﻿// deelx.h
//
// DEELX Regular Expression Engine (v1.2)
//
// Copyright 2006 ~ 2012 (c) RegExLab.com
// All Rights Reserved.
//
// http://www.regexlab.com/deelx/
//
// Author: 史寿伟 (sswater shi)
// sswater@gmail.com
//
// $Revision: 749 $
//

#ifndef __DEELX_REGEXP__H__
#define __DEELX_REGEXP__H__

#include <memory.h>
#include <ctype.h>
#include <limits.h>
#include <string.h>
#include <stdlib.h>

extern "C" {
    typedef int (*POSIX_FUNC)(int);
    //int isblank(int c);
}

//
// Data Reference
//
template <class ELT> class CBufferRefT
{
public:
    CBufferRefT(const ELT *pcsz, int length);
    CBufferRefT(const ELT *pcsz);

public:
    int nCompare(const ELT *pcsz, int len = 0) const;
    int nCompareNoCase(const ELT *pcsz, int len = 0) const;
    int  Compare(const ELT *pcsz, int len = 0) const;
    int  CompareNoCase(const ELT *pcsz, int len = 0) const;
    int  Compare(const CBufferRefT<ELT> &cref, int len = 0) const;
    int  CompareNoCase(const CBufferRefT<ELT> &cref, int len = 0) const;

    ELT At(int nIndex, ELT def = 0) const;
    ELT operator [](int nIndex) const;

    const ELT *GetBuffer() const;
    int GetSize() const;

public:
    virtual ~CBufferRefT();

    // Content
protected:
    ELT *m_pBuffer;
    int  m_nSize;
};

//
// Implemenation
//
template <class ELT> CBufferRefT<ELT>::CBufferRefT(const ELT *pcsz, int length)
{
    m_pBuffer  = (ELT *)pcsz;
    m_nSize = length;
}

template <class ELT> CBufferRefT<ELT>::CBufferRefT(const ELT *pcsz)
{
    m_pBuffer  = (ELT *)pcsz;
    m_nSize = 0;

    if (pcsz != 0) while (m_pBuffer[m_nSize] != 0) { ++m_nSize; }
}

template <class ELT> int CBufferRefT<ELT>::nCompare(const ELT *pcsz, int len) const
{
    len = (0 >= len || len > m_nSize) ? m_nSize : len;

    for (int i = 0; i < len; ++i)
    {
        if (m_pBuffer[i] != pcsz[i]) { return m_pBuffer[i] - pcsz[i]; }
    }

    return 0;
}

template <class ELT> int CBufferRefT<ELT>::nCompareNoCase(const ELT *pcsz, int len) const
{
    len = (0 >= len || len > m_nSize) ? m_nSize : len;

    for (int i = 0; i < len; ++i)
    {
        if (m_pBuffer[i] != pcsz[i])
        {
            if (toupper((int)m_pBuffer[i]) != toupper((int)pcsz[i]))
            { return m_pBuffer[i] - pcsz[i]; }
        }
    }

    return 0;
}

template <class ELT> inline int CBufferRefT<ELT>::Compare(const ELT *pcsz, int len) const
{
    return nCompare(pcsz, len) ? 1 : (int)pcsz[m_nSize];
}

template <class ELT> inline int CBufferRefT<ELT>::CompareNoCase(const ELT *pcsz, int len) const
{
    return nCompareNoCase(pcsz, len) ? 1 : (int)pcsz[m_nSize];
}

template <class ELT> inline int CBufferRefT<ELT>::Compare(const CBufferRefT<ELT> &cref, int len) const
{
    return m_nSize == cref.m_nSize ? nCompare(cref.GetBuffer(), len) : 1;
}

template<class ELT> inline int CBufferRefT<ELT> ::CompareNoCase(const CBufferRefT<ELT> &cref, int len) const
{
    return m_nSize == cref.m_nSize ? nCompareNoCase(cref.GetBuffer(), len) : 1;
}

template <class ELT> inline ELT CBufferRefT<ELT>::At(int nIndex, ELT def) const
{
    return nIndex >= m_nSize ? def : m_pBuffer[nIndex];
}

template <class ELT> inline ELT CBufferRefT<ELT>::operator [](int nIndex) const
{
    return nIndex >= m_nSize ? 0 : m_pBuffer[nIndex];
}

template <class ELT> const ELT *CBufferRefT<ELT>::GetBuffer() const
{
    static const ELT _def[] = {0}; return m_pBuffer ? m_pBuffer : _def;
}

template <class ELT> inline int CBufferRefT<ELT>::GetSize() const
{
    return m_nSize;
}

template <class ELT> CBufferRefT<ELT>::~CBufferRefT()
{
}

//
// Data Buffer
//
template <class ELT> class CBufferT : public CBufferRefT<ELT>
{
public:
    CBufferT(const ELT *pcsz, int length);
    CBufferT(const ELT *pcsz);
    CBufferT();

public:
    ELT  &operator [](int nIndex);
    const ELT &operator [](int nIndex) const;
    void  Append(const ELT *pcsz, int length, int eol = 0);
    void  Append(ELT el, int eol = 0);

public:
    void  Push(ELT el);
    void  Push(const CBufferRefT<ELT> &buf);
    int   Pop(ELT &el);
    int   Pop(CBufferT<ELT> &buf);
    int   Peek(ELT &el) const;

public:
    const ELT *GetBuffer() const;
    ELT  *GetBuffer();
    ELT  *Detach();
    void  Release();
    void  Prepare(int index, int fill = 0);
    void  Restore(int size);

    ELT *PrepareInsert(int nPos, int nSize)
    {
        int nOldSize = CBufferRefT<ELT>::m_nSize;
        Restore(nPos > CBufferRefT<ELT>::m_nSize ? nPos : CBufferRefT<ELT>::m_nSize + nSize);

        if (nPos < nOldSize)
        {
            ELT *from = CBufferRefT<ELT>::m_pBuffer + nPos, * to = CBufferRefT<ELT>::m_pBuffer + nPos + nSize;
            memmove(to, from, sizeof(ELT) * (nOldSize - nPos));
        }

        return CBufferRefT<ELT>::m_pBuffer + nPos;
    }

    void Insert(int nIndex, const ELT &rT)
    {
        Insert(nIndex, &rT, 1);
    }

    void Insert(int nIndex, const ELT *pT, int nSize)
    {
        memcpy(PrepareInsert(nIndex, nSize), pT, sizeof(ELT) * nSize);
    }

    void Remove(int nIndex)
    {
        Remove(nIndex, 1);
    }

    void Remove(int nIndex, int nSize)
    {
        if (nIndex < CBufferRefT<ELT>::m_nSize)
        {
            if (nIndex + nSize >= CBufferRefT<ELT>::m_nSize)
            {
                Restore(nIndex);
            }
            else
            {
                memmove(CBufferRefT<ELT>::m_pBuffer + nIndex, CBufferRefT<ELT>::m_pBuffer + nIndex + nSize,
                        sizeof(ELT) * (CBufferRefT<ELT>::m_nSize - nIndex - nSize));
                Restore(CBufferRefT<ELT>::m_nSize - nSize);
            }
        }
    }

    void SetMaxLength(int nSize)
    {
        if (nSize > m_nMaxLength)
        {
            if (m_nMaxLength < 8)     { m_nMaxLength = 8; }

            if (nSize > m_nMaxLength) { m_nMaxLength *= 2; }

            if (nSize > m_nMaxLength)
            {
                m_nMaxLength  = nSize + 11;
                m_nMaxLength -= m_nMaxLength & 0x07;
            }

            CBufferRefT<ELT>::m_pBuffer = (ELT *) realloc(CBufferRefT<ELT>::m_pBuffer, sizeof(ELT) * m_nMaxLength);
        }
    }

public:
    virtual ~CBufferT();

    // Content
protected:
    int   m_nMaxLength;
};

//
// Implemenation
//
template <class ELT> CBufferT<ELT>::CBufferT(const ELT *pcsz, int length) : CBufferRefT<ELT>(0, length)
{
    m_nMaxLength = CBufferRefT<ELT>::m_nSize + 1;

    CBufferRefT<ELT>::m_pBuffer = (ELT *) malloc(sizeof(ELT) * m_nMaxLength);
    memcpy(CBufferRefT<ELT>::m_pBuffer, pcsz, sizeof(ELT) * CBufferRefT<ELT>::m_nSize);
    CBufferRefT<ELT>::m_pBuffer[CBufferRefT<ELT>::m_nSize] = 0;
}

template <class ELT> CBufferT<ELT>::CBufferT(const ELT *pcsz) : CBufferRefT<ELT>(pcsz)
{
    m_nMaxLength = CBufferRefT<ELT>::m_nSize + 1;

    CBufferRefT<ELT>::m_pBuffer = (ELT *) malloc(sizeof(ELT) * m_nMaxLength);
    memcpy(CBufferRefT<ELT>::m_pBuffer, pcsz, sizeof(ELT) * CBufferRefT<ELT>::m_nSize);
    CBufferRefT<ELT>::m_pBuffer[CBufferRefT<ELT>::m_nSize] = 0;
}

template <class ELT> CBufferT<ELT>::CBufferT() : CBufferRefT<ELT>(0, 0)
{
    m_nMaxLength = 0;
    CBufferRefT<ELT>::m_pBuffer    = 0;
}

template <class ELT> inline ELT &CBufferT<ELT>::operator [](int nIndex)
{
    return CBufferRefT<ELT>::m_pBuffer[nIndex];
}

template <class ELT> inline const ELT &CBufferT<ELT>::operator [](int nIndex) const
{
    return CBufferRefT<ELT>::m_pBuffer[nIndex];
}

template <class ELT> void CBufferT<ELT>::Append(const ELT *pcsz, int length, int eol)
{
    int nNewLength = m_nMaxLength;

    // Check length
    if (nNewLength < 8) { nNewLength = 8; }

    if (CBufferRefT<ELT>::m_nSize + length + eol > nNewLength) { nNewLength *= 2; }

    if (CBufferRefT<ELT>::m_nSize + length + eol > nNewLength)
    {
        nNewLength  = CBufferRefT<ELT>::m_nSize + length + eol + 11;
        nNewLength -= nNewLength % 8;
    }

    // Realloc
    if (nNewLength > m_nMaxLength)
    {
        CBufferRefT<ELT>::m_pBuffer = (ELT *) realloc(CBufferRefT<ELT>::m_pBuffer, sizeof(ELT) * nNewLength);
        m_nMaxLength = nNewLength;
    }

    // Append
    memcpy(CBufferRefT<ELT>::m_pBuffer + CBufferRefT<ELT>::m_nSize, pcsz, sizeof(ELT) * length);
    CBufferRefT<ELT>::m_nSize += length;

    if (eol > 0) { CBufferRefT<ELT>::m_pBuffer[CBufferRefT<ELT>::m_nSize] = 0; }
}

template <class ELT> inline void CBufferT<ELT>::Append(ELT el, int eol)
{
    Append(&el, 1, eol);
}

template <class ELT> void CBufferT<ELT>::Push(ELT el)
{
    // Realloc
    if (CBufferRefT<ELT>::m_nSize >= m_nMaxLength)
    {
        int nNewLength = m_nMaxLength * 2;

        if (nNewLength < 8) { nNewLength = 8; }

        CBufferRefT<ELT>::m_pBuffer = (ELT *) realloc(CBufferRefT<ELT>::m_pBuffer, sizeof(ELT) * nNewLength);
        m_nMaxLength = nNewLength;
    }

    // Append
    CBufferRefT<ELT>::m_pBuffer[CBufferRefT<ELT>::m_nSize++] = el;
}

template <class ELT> void CBufferT<ELT>::Push(const CBufferRefT<ELT> &buf)
{
    for (int i = 0; i < buf.GetSize(); ++i) { Push(buf[i]); }

    Push((ELT)buf.GetSize());
}

template <class ELT> inline int CBufferT<ELT>::Pop(ELT &el)
{
    if (CBufferRefT<ELT>::m_nSize > 0)
    {
        el = CBufferRefT<ELT>::m_pBuffer[--CBufferRefT<ELT>::m_nSize];
        return 1;
    }
    else { return 0; }
}

template <class ELT> int CBufferT<ELT>::Pop(CBufferT<ELT> &buf)
{
    int size, res = 1;
    res = res && Pop(*(ELT *)&size);
    buf.Restore(size);

    for (int i = size - 1; i >= 0; --i)
    {
        res = res && Pop(buf[i]);
    }

    return res;
}

template <class ELT> inline int CBufferT<ELT>::Peek(ELT &el) const
{
    if (CBufferRefT<ELT>::m_nSize > 0)
    {
        el = CBufferRefT<ELT>::m_pBuffer[CBufferRefT<ELT>::m_nSize - 1];
        return 1;
    }
    else { return 0; }
}

template <class ELT> const ELT *CBufferT<ELT>::GetBuffer() const
{
    static const ELT _def[] = {0}; return CBufferRefT<ELT>::m_pBuffer ? CBufferRefT<ELT>::m_pBuffer : _def;
}

template <class ELT> ELT *CBufferT<ELT>::GetBuffer()
{
    static const ELT _def[] = {0}; return CBufferRefT<ELT>::m_pBuffer ? CBufferRefT<ELT>::m_pBuffer : (ELT *)_def;
}

template <class ELT> ELT *CBufferT<ELT>::Detach()
{
    ELT *pBuffer = CBufferRefT<ELT>::m_pBuffer;

    CBufferRefT<ELT>::m_pBuffer = 0;
    CBufferRefT<ELT>::m_nSize = m_nMaxLength = 0;

    return pBuffer;
}

template <class ELT> void CBufferT<ELT>::Release()
{
    ELT *pBuffer = Detach();

    if (pBuffer != 0) { free(pBuffer); }
}

template <class ELT> void CBufferT<ELT>::Prepare(int index, int fill)
{
    int nNewSize = index + 1;

    // Realloc
    if (nNewSize > m_nMaxLength)
    {
        int nNewLength = m_nMaxLength;

        if (nNewLength < 8)        { nNewLength = 8; }

        if (nNewSize > nNewLength) { nNewLength *= 2; }

        if (nNewSize > nNewLength)
        {
            nNewLength  = nNewSize + 11;
            nNewLength -= nNewLength % 8;
        }

        CBufferRefT<ELT>::m_pBuffer = (ELT *) realloc(CBufferRefT<ELT>::m_pBuffer, sizeof(ELT) * nNewLength);
        m_nMaxLength = nNewLength;
    }

    // size
    if (CBufferRefT<ELT>::m_nSize < nNewSize)
    {
        memset(CBufferRefT<ELT>::m_pBuffer + CBufferRefT<ELT>::m_nSize, fill,
               sizeof(ELT) * (nNewSize - CBufferRefT<ELT>::m_nSize));
        CBufferRefT<ELT>::m_nSize = nNewSize;
    }
}

template <class ELT> inline void CBufferT<ELT>::Restore(int size)
{
    SetMaxLength(size);
    CBufferRefT<ELT>::m_nSize = size;
}

template <class ELT> CBufferT<ELT>::~CBufferT()
{
    if (CBufferRefT<ELT>::m_pBuffer != 0) { free(CBufferRefT<ELT>::m_pBuffer); }
}

template <class T> class CSortedBufferT : public CBufferT <T>
{
public:
    CSortedBufferT(int reverse = 0);
    CSortedBufferT(int(*)(const void *, const void *));

public:
    void Add(const T &rT);
    void Add(const T *pT, int nSize);
    int  Remove(const T &rT);
    void RemoveAll();

    void SortFreeze() { m_bSortFreezed = 1; }
    void SortUnFreeze();

public:
    int  Find(const T &rT, int(* compare)(const void *, const void *) = 0) { return FindAs(*(T *)&rT, compare); }
    int  FindAs(const T &rT, int(*)(const void *, const void *) = 0);
    int  GetSize() const { return CBufferRefT<T>::m_nSize; }
    T &operator [](int nIndex) { return CBufferT <T>::operator [](nIndex); }

protected:
    int (* m_fncompare)(const void *, const void *);
    static int compareT(const void *, const void *);
    static int compareReverseT(const void *, const void *);

    int  m_bSortFreezed;
};

template <class T> CSortedBufferT <T>::CSortedBufferT(int reverse)
{
    m_fncompare = reverse ? compareReverseT : compareT;
    m_bSortFreezed = 0;
}

template <class T> CSortedBufferT <T>::CSortedBufferT(int (* compare)(const void *, const void *))
{
    m_fncompare = compare;
    m_bSortFreezed = 0;
}

template <class T> void CSortedBufferT <T>::Add(const T &rT)
{
    if (m_bSortFreezed != 0)
    {
        Append(rT);
        return;
    }

    int a = 0, b = CBufferRefT<T>::m_nSize - 1, c = CBufferRefT<T>::m_nSize / 2;

    while (a <= b)
    {
        int r = m_fncompare(&rT, &CBufferRefT<T>::m_pBuffer[c]);

        if (r < 0)      { b = c - 1; }
        else if (r > 0) { a = c + 1; }
        else            { break; }

        c = (a + b + 1) / 2;
    }

    Insert(c, rT);
}

template <class T> void CSortedBufferT <T>::Add(const T *pT, int nSize)
{
    Append(pT, nSize);

    if (m_bSortFreezed == 0)
    {
        qsort(CBufferRefT<T>::m_pBuffer, CBufferRefT<T>::m_nSize, sizeof(T), m_fncompare);
    }
}

template <class T> int CSortedBufferT <T>::FindAs(const T &rT, int(* compare)(const void *, const void *))
{
    const T *pT = (const T *)bsearch(&rT, CBufferRefT<T>::m_pBuffer, CBufferRefT<T>::m_nSize, sizeof(T),
                                     compare == 0 ? m_fncompare : compare);

    if (pT != NULL) { return pT - CBufferRefT<T>::m_pBuffer; }
    else            { return -1; }
}

template <class T> int CSortedBufferT <T>::Remove(const T &rT)
{
    int pos = Find(rT);

    if (pos >= 0) { CBufferT <T>::Remove(pos); }

    return pos;
}

template <class T> inline void CSortedBufferT <T>::RemoveAll()
{
    CBufferT<T>::Restore(0);
}

template <class T> void CSortedBufferT <T>::SortUnFreeze()
{
    if (m_bSortFreezed != 0)
    {
        m_bSortFreezed = 0;
        qsort(CBufferRefT<T>::m_pBuffer, CBufferRefT<T>::m_nSize, sizeof(T), m_fncompare);
    }
}

template <class T> int CSortedBufferT <T>::compareT(const void *elem1, const void *elem2)
{
    if (*(const T *)elem1 == *(const T *)elem2)      { return 0; }
    else if (*(const T *)elem1 < * (const T *)elem2) { return -1; }
    else                                             { return 1; }
}

template <class T> int CSortedBufferT <T>::compareReverseT(const void *elem1, const void *elem2)
{
    if (*(const T *)elem1 == *(const T *)elem2)     { return 0; }
    else if (*(const T *)elem1 > *(const T *)elem2) { return -1; }
    else                                            { return 1; }
}

//
// Context
//
class CContext
{
public:
    CBufferT <int> m_stack;
    CBufferT <int> m_capturestack, m_captureindex;

public:
    int    m_nCurrentPos;
    int    m_nBeginPos;
    int    m_nLastBeginPos;
    int    m_nParenZindex;

    void  *m_pMatchString;
    int    m_pMatchStringLength;
};

class CContextShot
{
public:
    CContextShot(CContext *pContext)
    {
        m_nCurrentPos = pContext->m_nCurrentPos;
        nsize  = pContext->m_stack.GetSize();
        ncsize = pContext->m_capturestack.GetSize();
    }

    void Restore(CContext *pContext)
    {
        pContext->m_stack.Restore(nsize);
        pContext->m_capturestack.Restore(ncsize);
        pContext->m_nCurrentPos = m_nCurrentPos;
    }

public:
    int m_nCurrentPos;
    int nsize;
    int ncsize;
};

//
// Interface
//
class ElxInterface
{
public:
    virtual int Match(CContext *pContext) const = 0;
    virtual int MatchNext(CContext *pContext) const = 0;

public:
    virtual ~ElxInterface() {};
};

//
// Alternative
//
template <int x> class CAlternativeElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CAlternativeElxT();

public:
    CBufferT <ElxInterface *> m_elxlist;
};

typedef CAlternativeElxT <0> CAlternativeElx;

//
// Assert
//
template <int x> class CAssertElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CAssertElxT(ElxInterface *pelx, int byes = 1);

public:
    ElxInterface *m_pelx;
    int m_byes;
};

typedef CAssertElxT <0> CAssertElx;

//
// Back reference elx
//
template <class CHART> class CBackrefElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CBackrefElxT(int nnumber, int brightleft, int bignorecase);

public:
    int m_nnumber;
    int m_brightleft;
    int m_bignorecase;

    CBufferT <CHART> m_szNamed;
};

//
// Implementation
//
template <class CHART> CBackrefElxT <CHART>::CBackrefElxT(int nnumber, int brightleft, int bignorecase)
{
    m_nnumber     = nnumber;
    m_brightleft  = brightleft;
    m_bignorecase = bignorecase;
}

template <class CHART> int CBackrefElxT <CHART>::Match(CContext *pContext) const
{
    // check number, for named
    if (m_nnumber < 0 || m_nnumber >= pContext->m_captureindex.GetSize()) { return 0; }

    int index = pContext->m_captureindex[m_nnumber];

    if (index < 0) { return 0; }

    // check enclosed
    int pos1 = pContext->m_capturestack[index + 1];
    int pos2 = pContext->m_capturestack[index + 2];

    if (pos2 < 0) { pos2 = pContext->m_nCurrentPos; }

    // info
    int lpos = pos1 < pos2 ? pos1 : pos2;
    int rpos = pos1 < pos2 ? pos2 : pos1;
    int slen = rpos - lpos;

    const CHART *pcsz = (const CHART *)pContext->m_pMatchString;
    int npos = pContext->m_nCurrentPos;
    int tlen = pContext->m_pMatchStringLength;

    // compare
    int bsucc;
    CBufferRefT <CHART> refstr(pcsz + lpos, slen);

    if (m_brightleft)
    {
        // 2019-04-22 zhuyadong 仅用于编辑框正则过滤，比较到字符串结尾。
        // if (npos < slen) { return 0; }

        if (m_bignorecase) { bsucc = !refstr.nCompareNoCase(pcsz + (npos - slen), tlen); }
        else               { bsucc = !refstr.nCompare(pcsz + (npos - slen), tlen); }

        if (bsucc)
        {
            pContext->m_stack.Push(npos);
            pContext->m_nCurrentPos -= (tlen > slen) ? slen : tlen;
        }

        //if (npos < slen) { return 0; }
        //if (m_bignorecase) { bsucc = ! refstr.nCompareNoCase(pcsz + (npos - slen)); }
        //else { bsucc = ! refstr.nCompare(pcsz + (npos - slen)); }
        //if (bsucc)
        //{
        //    pContext->m_stack.Push(npos);
        //    pContext->m_nCurrentPos -= slen;
        //}
    }
    else
    {
        // 2019-04-22 zhuyadong 仅用于编辑框正则过滤，比较到字符串结尾。
        // if (npos + slen > tlen) { return 0; }

        if (m_bignorecase) { bsucc = !refstr.nCompareNoCase(pcsz + npos, tlen); }
        else               { bsucc = !refstr.nCompare(pcsz + npos, tlen); }

        if (bsucc)
        {
            pContext->m_stack.Push(npos);
            pContext->m_nCurrentPos += (tlen > slen) ? slen : tlen;
        }

        //if (npos + slen > tlen) { return 0; }
        //if (m_bignorecase) { bsucc = ! refstr.nCompareNoCase(pcsz + npos); }
        //else { bsucc = ! refstr.nCompare(pcsz + npos); }
        //if (bsucc)
        //{
        //    pContext->m_stack.Push(npos);
        //    pContext->m_nCurrentPos += slen;
        //}
    }

    return bsucc;
}

template <class CHART> int CBackrefElxT <CHART>::MatchNext(CContext *pContext) const
{
    int npos = 0;

    pContext->m_stack.Pop(npos);
    pContext->m_nCurrentPos = npos;

    return 0;
}

// RCHART
#ifndef RCHART
    #define RCHART(ch) ((CHART)ch)
#endif

// BOUNDARY_TYPE
enum BOUNDARY_TYPE
{
    BOUNDARY_FILE_BEGIN, // begin of whole text
    BOUNDARY_FILE_END,   // end of whole text
    BOUNDARY_FILE_END_N, // end of whole text, or before newline at the end
    BOUNDARY_LINE_BEGIN, // begin of line
    BOUNDARY_LINE_END,   // end of line
    BOUNDARY_WORD_BEGIN, // begin of word
    BOUNDARY_WORD_END,   // end of word
    BOUNDARY_WORD_EDGE
};

//
// Boundary Elx
//
template <class CHART> class CBoundaryElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CBoundaryElxT(int ntype, int byes = 1);

protected:
    static int IsWordChar(CHART ch);

public:
    int m_ntype;
    int m_byes;
};

//
// Implementation
//
template <class CHART> CBoundaryElxT <CHART>::CBoundaryElxT(int ntype, int byes)
{
    m_ntype = ntype;
    m_byes  = byes;
}

template <class CHART> int CBoundaryElxT <CHART>::Match(CContext *pContext) const
{
    const CHART *pcsz  = (const CHART *)pContext->m_pMatchString;
    int npos = pContext->m_nCurrentPos;
    int tlen = pContext->m_pMatchStringLength;

    CHART chL = npos > 0    ? pcsz[npos - 1] : 0;
    CHART chR = npos < tlen ? pcsz[npos    ] : 0;

    int bsucc = 0;

    switch (m_ntype)
    {
    case BOUNDARY_FILE_BEGIN:
        bsucc = (npos <= 0);
        break;

    case BOUNDARY_FILE_END:
        bsucc = (npos >= tlen);
        break;

    case BOUNDARY_FILE_END_N:
        bsucc = (npos >= tlen) || (pcsz[tlen - 1] == RCHART('\n') && (npos == tlen - 1 ||
                                   (pcsz[tlen - 2] == RCHART('\r') && npos == tlen - 2)));
        break;

    case BOUNDARY_LINE_BEGIN:
        bsucc = (npos <= 0) || (chL == RCHART('\n')) || ((chL == RCHART('\r')) && (chR != RCHART('\n')));
        break;

    case BOUNDARY_LINE_END:
        bsucc = (npos >= tlen) || (chR == RCHART('\r')) || ((chR == RCHART('\n')) && (chL != RCHART('\r')));
        break;

    case BOUNDARY_WORD_BEGIN:
        bsucc = !IsWordChar(chL) &&   IsWordChar(chR);
        break;

    case BOUNDARY_WORD_END:
        bsucc =   IsWordChar(chL) && !IsWordChar(chR);
        break;

    case BOUNDARY_WORD_EDGE:
        bsucc =   IsWordChar(chL) ?  !IsWordChar(chR) : IsWordChar(chR);
        break;
    }

    return m_byes ? bsucc : !bsucc;
}

template <class CHART> int CBoundaryElxT <CHART>::MatchNext(CContext *) const
{
    return 0;
}

template <class CHART> inline int CBoundaryElxT <CHART>::IsWordChar(CHART ch)
{
    return (ch >= RCHART('A') && ch <= RCHART('Z')) || (ch >= RCHART('a') && ch <= RCHART('z')) ||
           (ch >= RCHART('0') && ch <= RCHART('9')) || (ch == RCHART('_'));
}

//
// Bracket
//
template <class CHART> class CBracketElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CBracketElxT(int nnumber, int bright);
    static int CheckCaptureIndex(int &index, CContext *pContext, int number);

public:
    int m_nnumber;
    int m_bright;

    CBufferT <CHART> m_szNamed;
};

template <class CHART> CBracketElxT <CHART>::CBracketElxT(int nnumber, int bright)
{
    m_nnumber = nnumber;
    m_bright  = bright;
}

template <class CHART> inline int CBracketElxT <CHART>::CheckCaptureIndex(int &index, CContext *pContext,
        int number)
{
    if (index >= pContext->m_capturestack.GetSize())
    { index  = pContext->m_capturestack.GetSize() - 4; }

    while (index >= 0)
    {
        if (pContext->m_capturestack[index] == number) { return 1; }

        index -= 4;
    }


    return 0;
}

//
// capturestack[index+0] => Group number
// capturestack[index+1] => Capture start pos
// capturestack[index+2] => Capture end pos
// capturestack[index+3] => Capture enclose z-index, zindex<0 means inner group with same name
//
template <class CHART> int CBracketElxT <CHART>::Match(CContext *pContext) const
{
    // check, for named
    if (m_nnumber < 0) { return 0; }

    if (!m_bright)
    {
        pContext->m_captureindex.Prepare(m_nnumber, -1);
        int index = pContext->m_captureindex[m_nnumber];

        // check
        if (CheckCaptureIndex(index, pContext, m_nnumber) && pContext->m_capturestack[index + 2] < 0)
        {
            --pContext->m_capturestack[index + 3];
            return 1;
        }

        // save
        pContext->m_captureindex[m_nnumber] = pContext->m_capturestack.GetSize();

        pContext->m_capturestack.Push(m_nnumber);
        pContext->m_capturestack.Push(pContext->m_nCurrentPos);
        pContext->m_capturestack.Push(-1);
        pContext->m_capturestack.Push(0);  // z-index
    }
    else
    {
        // check
        int index = pContext->m_captureindex[m_nnumber];

        if (CheckCaptureIndex(index, pContext, m_nnumber))
        {
            if (pContext->m_capturestack[index + 3] < 0) // check inner group with same name
            {
                ++pContext->m_capturestack[index + 3];
                return 1;
            }

            // save
            pContext->m_capturestack[index + 2] = pContext->m_nCurrentPos;
            pContext->m_capturestack[index + 3] = pContext->m_nParenZindex++;
        }
    }

    return 1;
}

template <class CHART> int CBracketElxT <CHART>::MatchNext(CContext *pContext) const
{
    int index = pContext->m_captureindex[m_nnumber];

    if (!CheckCaptureIndex(index, pContext, m_nnumber)) { return 0; }

    if (!m_bright)
    {
        if (pContext->m_capturestack[index + 3] < 0)
        {
            ++pContext->m_capturestack[index + 3];
            return 0;
        }

        pContext->m_capturestack.Restore(pContext->m_capturestack.GetSize() - 4);

        // to find
        CheckCaptureIndex(index, pContext, m_nnumber);

        // new index
        pContext->m_captureindex[m_nnumber] = index;
    }
    else
    {
        if (pContext->m_capturestack[index + 2] >= 0)
        {
            pContext->m_capturestack[index + 2] = -1;
            pContext->m_capturestack[index + 3] =  0;
        }
        else
        {
            --pContext->m_capturestack[index + 3];
        }
    }

    return 0;
}

//
// Deletage
//
template <class CHART> class CDelegateElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CDelegateElxT(int ndata = 0);

public:
    ElxInterface *m_pelx;
    int m_ndata; // +0 : recursive to
    // -3 : named recursive

    CBufferT <CHART> m_szNamed;
};

template <class CHART> CDelegateElxT <CHART>::CDelegateElxT(int ndata)
{
    m_pelx  = 0;
    m_ndata = ndata;
}

template <class CHART> int CDelegateElxT <CHART>::Match(CContext *pContext) const
{
    if (m_pelx != 0) { return m_pelx->Match(pContext); }
    else             { return 1; }
}

template <class CHART> int CDelegateElxT <CHART>::MatchNext(CContext *pContext) const
{
    if (m_pelx != 0) { return m_pelx->MatchNext(pContext); }
    else             { return 0; }
}

//
// Empty
//
template <int x> class CEmptyElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CEmptyElxT();
};

typedef CEmptyElxT <0> CEmptyElx;

//
// Global
//
template <int x> class CGlobalElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CGlobalElxT();
};

typedef CGlobalElxT <0> CGlobalElx;

//
// Repeat
//
template <int x> class CRepeatElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CRepeatElxT(ElxInterface *pelx, int ntimes);

protected:
    int MatchFixed(CContext *pContext) const;
    int MatchNextFixed(CContext *pContext) const;
    int MatchForward(CContext *pContext) const
    {
        CContextShot shot(pContext);

        if (!m_pelx->Match(pContext))                      { return 0; }

        if (pContext->m_nCurrentPos != shot.m_nCurrentPos) { return 1; }

        if (!m_pelx->MatchNext(pContext))                  { return 0; }

        if (pContext->m_nCurrentPos != shot.m_nCurrentPos) { return 1; }

        shot.Restore(pContext);
        return 0;
    }

public:
    ElxInterface *m_pelx;
    int m_nfixed;
};

typedef CRepeatElxT <0> CRepeatElx;

//
// Greedy
//
template <int x> class CGreedyElxT : public CRepeatElxT <x>
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CGreedyElxT(ElxInterface *pelx, int nmin = 0, int nmax = INT_MAX);

protected:
    int MatchVart(CContext *pContext) const;
    int MatchNextVart(CContext *pContext) const;

public:
    int m_nvart;
};

typedef CGreedyElxT <0> CGreedyElx;

//
// Independent
//
template <int x> class CIndependentElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CIndependentElxT(ElxInterface *pelx);

public:
    ElxInterface *m_pelx;
};

typedef CIndependentElxT <0> CIndependentElx;

//
// List
//
template <int x> class CListElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CListElxT(int brightleft);

public:
    CBufferT <ElxInterface *> m_elxlist;
    int m_brightleft;
};

typedef CListElxT <0> CListElx;

//
// Posix Elx
//
template <class CHART> class CPosixElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CPosixElxT(const char *posix, int brightleft);

public:
    POSIX_FUNC m_posixfun;
    int m_brightleft;
    int m_byes;
};

//
// Implementation
//
template <class CHART> CPosixElxT <CHART>::CPosixElxT(const char *posix, int brightleft)
{
    m_brightleft = brightleft;

    if (posix[1] == '^')
    {
        m_byes = 0;
        posix += 2;
    }
    else
    {
        m_byes = 1;
        posix += 1;
    }

    if (!strncmp(posix, "alnum:", 6))  { m_posixfun = ::isalnum; }
    else if (!strncmp(posix, "alpha:", 6))  { m_posixfun = ::isalpha; }
    else if (!strncmp(posix, "ascii:", 6))  { m_posixfun = ::isascii; }
    else if (!strncmp(posix, "cntrl:", 6))  { m_posixfun = ::iscntrl; }
    else if (!strncmp(posix, "digit:", 6))  { m_posixfun = ::isdigit; }
    else if (!strncmp(posix, "graph:", 6))  { m_posixfun = ::isgraph; }
    else if (!strncmp(posix, "lower:", 6))  { m_posixfun = ::islower; }
    else if (!strncmp(posix, "print:", 6))  { m_posixfun = ::isprint; }
    else if (!strncmp(posix, "punct:", 6))  { m_posixfun = ::ispunct; }
    else if (!strncmp(posix, "space:", 6))  { m_posixfun = ::isspace; }
    else if (!strncmp(posix, "upper:", 6))  { m_posixfun = ::isupper; }
    else if (!strncmp(posix, "xdigit:", 7)) { m_posixfun = ::isxdigit; }
    else if (!strncmp(posix, "blank:", 6))  { m_posixfun = isblank; }
    else                                    { m_posixfun = 0; }
}

inline int isblank(int c)
{
    return c == 0x20 || c == '\t';
}

template <class CHART> int CPosixElxT <CHART>::Match(CContext *pContext) const
{
    if (m_posixfun == 0) { return 0; }

    int tlen = pContext->m_pMatchStringLength;
    int npos = pContext->m_nCurrentPos;

    // check
    int at   = m_brightleft ? npos - 1 : npos;

    if (at < 0 || at >= tlen) { return 0; }

    CHART ch = ((const CHART *)pContext->m_pMatchString)[at];

    int bsucc = (*m_posixfun)(ch);

    if (!m_byes) { bsucc = !bsucc; }

    if (bsucc) { pContext->m_nCurrentPos += m_brightleft ? -1 : 1; }

    return bsucc;
}

template <class CHART> int CPosixElxT <CHART>::MatchNext(CContext *pContext) const
{
    pContext->m_nCurrentPos -= m_brightleft ? -1 : 1;
    return 0;
}

//
// Possessive
//
template <int x> class CPossessiveElxT : public CGreedyElxT <x>
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CPossessiveElxT(ElxInterface *pelx, int nmin = 0, int nmax = INT_MAX);
};

typedef CPossessiveElxT <0> CPossessiveElx;

//
// Range Elx
//
template <class CHART> class CRangeElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CRangeElxT(int brightleft, int byes);

public:
    int IsContainChar(CHART ch) const;

public:
    CBufferT <CHART> m_ranges;
    CBufferT <CHART> m_chars;
    CBufferT <ElxInterface *> m_embeds;

public:
    int m_brightleft;
    int m_byes;
};

//
// Implementation
//
template <class CHART> CRangeElxT <CHART>::CRangeElxT(int brightleft, int byes)
{
    m_brightleft = brightleft;
    m_byes       = byes;
}

template <class CHART> int CRangeElxT <CHART>::Match(CContext *pContext) const
{
    int tlen = pContext->m_pMatchStringLength;
    int npos = pContext->m_nCurrentPos;

    // check
    int at   = m_brightleft ? npos - 1 : npos;

    if (at < 0 || at >= tlen) { return 0; }

    CHART ch = ((const CHART *)pContext->m_pMatchString)[at];
    int bsucc = 0, i;

    // compare
    for (i = 0; !bsucc && i < m_ranges.GetSize(); i += 2)
    {
        if (m_ranges[i] <= ch && ch <= m_ranges[i + 1]) { bsucc = 1; }
    }

    for (i = 0; !bsucc && i < m_chars.GetSize(); ++i)
    {
        if (m_chars[i] == ch) { bsucc = 1; }
    }

    for (i = 0; !bsucc && i < m_embeds.GetSize(); ++i)
    {
        if (m_embeds[i]->Match(pContext))
        {
            pContext->m_nCurrentPos = npos;
            bsucc = 1;
        }
    }

    if (!m_byes) { bsucc = !bsucc; }

    if (bsucc)    { pContext->m_nCurrentPos += m_brightleft ? -1 : 1; }

    return bsucc;
}

template <class CHART> int CRangeElxT <CHART>::IsContainChar(CHART ch) const
{
    int bsucc = 0, i;

    // compare
    for (i = 0; !bsucc && i < m_ranges.GetSize(); i += 2)
    {
        if (m_ranges[i] <= ch && ch <= m_ranges[i + 1]) { bsucc = 1; }
    }

    for (i = 0; !bsucc && i < m_chars.GetSize(); ++i)
    {
        if (m_chars[i] == ch) { bsucc = 1; }
    }

    return bsucc;
}

template <class CHART> int CRangeElxT <CHART>::MatchNext(CContext *pContext) const
{
    pContext->m_nCurrentPos -= m_brightleft ? -1 : 1;
    return 0;
}

//
// Reluctant
//
template <int x> class CReluctantElxT : public CRepeatElxT <x>
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CReluctantElxT(ElxInterface *pelx, int nmin = 0, int nmax = INT_MAX);

protected:
    int MatchVart(CContext *pContext) const;
    int MatchNextVart(CContext *pContext) const;

public:
    int m_nvart;
};

typedef CReluctantElxT <0> CReluctantElx;

//
// String Elx
//
template <class CHART> class CStringElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CStringElxT(const CHART *fixed, int nlength, int brightleft, int bignorecase);

public:
    CBufferT <CHART> m_szPattern;
    int m_brightleft;
    int m_bignorecase;
};

//
// Implementation
//
template <class CHART>
CStringElxT<CHART>::CStringElxT(const CHART *fixed, int nlength, int brightleft, int bignorecase)
    : m_szPattern(fixed, nlength)
{
    m_brightleft  = brightleft;
    m_bignorecase = bignorecase;
}

template <class CHART> int CStringElxT <CHART>::Match(CContext *pContext) const
{
    const CHART *pcsz  = (const CHART *)pContext->m_pMatchString;
    int npos = pContext->m_nCurrentPos;
    int tlen = pContext->m_pMatchStringLength;
    int slen = m_szPattern.GetSize();

    int bsucc = false;

    if (m_brightleft)
    {
        // 2019-04-22 zhuyadong 仅用于编辑框正则过滤，比较到字符串结尾。
        // if (npos < slen) { return 0; }

        if (m_bignorecase) { bsucc = !m_szPattern.nCompareNoCase(pcsz + (npos - slen), tlen); }
        else               { bsucc = !m_szPattern.nCompare(pcsz + (npos - slen), tlen); }

        if (bsucc) { pContext->m_nCurrentPos -= (tlen > slen) ? slen : tlen; }

        //if (npos < slen) { return 0; }
        //if (m_bignorecase) { bsucc = !m_szPattern.nCompareNoCase(pcsz + (npos - slen)); }
        //else { bsucc = !m_szPattern.nCompare(pcsz + (npos - slen)); }
        //if (bsucc) { pContext->m_nCurrentPos -= slen; }
    }
    else
    {
        // 2019-04-22 zhuyadong 仅用于编辑框正则过滤，比较到字符串结尾。
        // if (npos + slen > tlen) { return 0; }

        if (m_bignorecase) { bsucc = !m_szPattern.nCompareNoCase(pcsz + npos, tlen); }
        else               { bsucc = !m_szPattern.nCompare(pcsz + npos, tlen); }

        if (bsucc) { pContext->m_nCurrentPos += (tlen > slen) ? slen : tlen; }

        //if (npos + slen > tlen)
        //{ return 0; }
        //if (m_bignorecase) { bsucc = ! m_szPattern.nCompareNoCase(pcsz + npos); }
        //else { bsucc = ! m_szPattern.nCompare(pcsz + npos); }
        //if (bsucc) { pContext->m_nCurrentPos += slen; }
    }

    return bsucc;
}

template <class CHART> int CStringElxT <CHART>::MatchNext(CContext *pContext) const
{
    int slen = m_szPattern.GetSize();

    if (m_brightleft) { pContext->m_nCurrentPos += slen; }
    else              { pContext->m_nCurrentPos -= slen; }

    return 0;
}

//
// CConditionElx
//
template <class CHART> class CConditionElxT : public ElxInterface
{
public:
    int Match(CContext *pContext) const;
    int MatchNext(CContext *pContext) const;

public:
    CConditionElxT();

public:
    // backref condition
    int m_nnumber;
    CBufferT <CHART> m_szNamed;

    // elx condition
    ElxInterface *m_pelxask;

    // selection
    ElxInterface *m_pelxyes, * m_pelxno;
};

template <class CHART> CConditionElxT <CHART>::CConditionElxT()
{
    m_nnumber = -1;
}

template <class CHART> int CConditionElxT <CHART>::Match(CContext *pContext) const
{
    // status
    int nbegin = pContext->m_nCurrentPos;
    int nsize  = pContext->m_stack.GetSize();
    int ncsize = pContext->m_capturestack.GetSize();

    // condition result
    int condition_yes = 0;

    // backref type
    if (m_nnumber >= 0)
    {
        do
        {
            if (m_nnumber >= pContext->m_captureindex.GetSize()) { break; }

            int index = pContext->m_captureindex[m_nnumber];

            if (index < 0) { break; }

            // else valid
            condition_yes = 1;
        } while (0);
    }
    else
    {
        if (m_pelxask == 0) { condition_yes = 1; }
        else                { condition_yes = m_pelxask->Match(pContext); }

        pContext->m_stack.Restore(nsize);
        pContext->m_nCurrentPos = nbegin;
    }

    // elx result
    int bsucc;

    if (condition_yes) { bsucc = m_pelxyes == 0 ? 1 : m_pelxyes->Match(pContext); }
    else               { bsucc = m_pelxno  == 0 ? 1 : m_pelxno ->Match(pContext); }

    if (bsucc)
    {
        pContext->m_stack.Push(ncsize);
        pContext->m_stack.Push(condition_yes);
    }
    else
    {
        pContext->m_capturestack.Restore(ncsize);
    }

    return bsucc;
}

template <class CHART> int CConditionElxT <CHART>::MatchNext(CContext *pContext) const
{
    // pop
    int ncsize, condition_yes;

    pContext->m_stack.Pop(condition_yes);
    pContext->m_stack.Pop(ncsize);

    // elx result
    int bsucc;

    if (condition_yes) { bsucc = m_pelxyes == 0 ? 0 : m_pelxyes->MatchNext(pContext); }
    else               { bsucc = m_pelxno  == 0 ? 0 : m_pelxno ->MatchNext(pContext); }

    if (bsucc)
    {
        pContext->m_stack.Push(ncsize);
        pContext->m_stack.Push(condition_yes);
    }
    else
    {
        pContext->m_capturestack.Restore(ncsize);
    }

    return bsucc;
}

//
// MatchResult
//
template <int x> class MatchResultT
{
public:
    int IsMatched() const;

public:
    int GetStart() const;
    int GetEnd() const;

public:
    int MaxGroupNumber() const;
    int GetGroupStart(int nGroupNumber) const;
    int GetGroupEnd(int nGroupNumber) const;

public:
    MatchResultT(const MatchResultT <x> &from) { *this = from; }
    MatchResultT(CContext *pContext = 0, int nMaxNumber = -1);
    MatchResultT <x> &operator = (const MatchResultT <x> &);
    inline operator int() const { return IsMatched(); }

public:
    CBufferT <int> m_result;
};

typedef MatchResultT <0> MatchResult;

// Stocked Elx IDs
enum STOCKELX_ID_DEFINES
{
    STOCKELX_EMPTY = 0,

    ///////////////////////

    STOCKELX_DOT_ALL,
    STOCKELX_DOT_NOT_ALL,

    STOCKELX_WORD,
    STOCKELX_WORD_NOT,

    STOCKELX_SPACE,
    STOCKELX_SPACE_NOT,

    STOCKELX_DIGITAL,
    STOCKELX_DIGITAL_NOT,

    //////////////////////

    STOCKELX_DOT_ALL_RIGHTLEFT,
    STOCKELX_DOT_NOT_ALL_RIGHTLEFT,

    STOCKELX_WORD_RIGHTLEFT,
    STOCKELX_WORD_RIGHTLEFT_NOT,

    STOCKELX_SPACE_RIGHTLEFT,
    STOCKELX_SPACE_RIGHTLEFT_NOT,

    STOCKELX_DIGITAL_RIGHTLEFT,
    STOCKELX_DIGITAL_RIGHTLEFT_NOT,

    /////////////////////

    STOCKELX_COUNT
};

// REGEX_FLAGS
#ifndef _REGEX_FLAGS_DEFINED
enum REGEX_FLAGS
{
    NO_FLAG        = 0,
    SINGLELINE     = 0x01,
    MULTILINE      = 0x02,
    GLOBAL         = 0x04,
    IGNORECASE     = 0x08,
    RIGHTTOLEFT    = 0x10,
    EXTENDED       = 0x20
};
#define _REGEX_FLAGS_DEFINED
#endif

//
// Builder T
//
template <class CHART> class CBuilderT
{
public:
    typedef CDelegateElxT  <CHART> CDelegateElx;
    typedef CBracketElxT   <CHART> CBracketElx;
    typedef CBackrefElxT   <CHART> CBackrefElx;
    typedef CConditionElxT <CHART> CConditionElx;

    // Methods
public:
    ElxInterface *Build(const CBufferRefT <CHART> &pattern, int flags);
    int GetNamedNumber(const CBufferRefT <CHART> &named) const;
    void Clear();

public:
    CBuilderT();
    ~CBuilderT();

    // Public Attributes
public:
    ElxInterface  *m_pTopElx;
    int            m_nFlags;
    int            m_nMaxNumber;
    int            m_nNextNamed;
    int            m_nGroupCount;

    CBufferT <ElxInterface *>  m_objlist;
    CBufferT <ElxInterface *>  m_grouplist;
    CBufferT <CDelegateElx *>  m_recursivelist;
    CBufferT <CListElx *>      m_namedlist;
    CBufferT <CBackrefElx *>   m_namedbackreflist;
    CBufferT <CConditionElx *> m_namedconditionlist;

    // CHART_INFO
protected:
    struct CHART_INFO
    {
    public:
        CHART ch;
        int   type;
        int   pos;
        int   len;

    public:
        CHART_INFO(CHART c, int t, int p = 0, int l = 0) { ch = c; type = t; pos = p; len = l;    }
        inline int operator == (const CHART_INFO &ci)    { return ch == ci.ch && type == ci.type; }
        inline int operator != (const CHART_INFO &ci)    { return !operator == (ci);             }
    };

protected:
    static unsigned int Hex2Int(const CHART *pcsz, int length, int &used);
    static int ReadDec(char *&str, unsigned int &dec);
    void MoveNext();
    int  GetNext2();

    ElxInterface *BuildAlternative(int vaflags);
    ElxInterface *BuildList(int &flags);
    ElxInterface *BuildRepeat(int &flags);
    ElxInterface *BuildSimple(int &flags);
    ElxInterface *BuildCharset(int &flags);
    ElxInterface *BuildRecursive(int &flags);
    ElxInterface *BuildBoundary(int &flags);
    ElxInterface *BuildBackref(int &flags);

    ElxInterface *GetStockElx(int nStockId);
    ElxInterface *Keep(ElxInterface *pElx);

    // Private Attributes
protected:
    CBufferRefT <CHART> m_pattern;
    CHART_INFO prev, curr, next, nex2;
    int m_nNextPos;
    int m_nCharsetDepth;
    int m_bQuoted;
    POSIX_FUNC m_quote_fun;

    ElxInterface *m_pStockElxs[STOCKELX_COUNT];
};

//
// Implementation
//
template <class CHART> CBuilderT <CHART>::CBuilderT() : m_pattern(0, 0), prev(0, 0), curr(0, 0), next(0, 0),
    nex2(0, 0)
{
    Clear();
}

template <class CHART> CBuilderT <CHART>::~CBuilderT()
{
    Clear();
}

template <class CHART> int CBuilderT <CHART>::GetNamedNumber(const CBufferRefT <CHART> &named) const
{
    for (int i = 0; i < m_namedlist.GetSize(); ++i)
    {
        if (!((CBracketElx *)m_namedlist[i]->m_elxlist[0])->m_szNamed.CompareNoCase(named))
        { return ((CBracketElx *)m_namedlist[i]->m_elxlist[0])->m_nnumber; }
    }

    return -3;
}

template <class CHART> ElxInterface *CBuilderT <CHART>::Build(const CBufferRefT <CHART> &pattern, int flags)
{
    // init
    m_pattern       = pattern;
    m_nNextPos      = 0;
    m_nCharsetDepth = 0;
    m_nMaxNumber    = 0;
    m_nNextNamed    = 0;
    m_nFlags        = flags;
    m_bQuoted       = 0;
    m_quote_fun     = 0;

    m_grouplist         .Restore(0);
    m_recursivelist     .Restore(0);
    m_namedlist         .Restore(0);
    m_namedbackreflist  .Restore(0);
    m_namedconditionlist.Restore(0);

    int i;

    for (i = 0; i < 3; ++i) { MoveNext(); }

    // build
    m_pTopElx = BuildAlternative(flags);

    // group 0
    m_grouplist.Prepare(0);
    m_grouplist[0] = m_pTopElx;

    // append named to unnamed
    m_nGroupCount = m_grouplist.GetSize();

    m_grouplist.Prepare(m_nMaxNumber + m_namedlist.GetSize());

    for (i = 0; i < m_namedlist.GetSize(); ++i)
    {
        CBracketElx *pleft  = (CBracketElx *)m_namedlist[i]->m_elxlist[0];
        CBracketElx *pright = (CBracketElx *)m_namedlist[i]->m_elxlist[2];

        // append
        m_grouplist[m_nGroupCount ++] = m_namedlist[i];

        if (pleft->m_nnumber > 0) { continue; }

        // same name
        int find_same_name = GetNamedNumber(pleft->m_szNamed);

        if (find_same_name >= 0)
        {
            pleft ->m_nnumber = find_same_name;
            pright->m_nnumber = find_same_name;
        }
        else
        {
            ++m_nMaxNumber;

            pleft ->m_nnumber = m_nMaxNumber;
            pright->m_nnumber = m_nMaxNumber;
        }
    }

    for (i = 1; i < m_nGroupCount; ++i)
    {
        CBracketElx *pleft = (CBracketElx *)((CListElx *)m_grouplist[i])->m_elxlist[0];

        if (pleft->m_nnumber > m_nMaxNumber) { m_nMaxNumber = pleft->m_nnumber; }
    }

    // connect recursive
    for (i = 0; i < m_recursivelist.GetSize(); ++i)
    {
        if (m_recursivelist[i]->m_ndata == -3)
        { m_recursivelist[i]->m_ndata = GetNamedNumber(m_recursivelist[i]->m_szNamed); }

        if (m_recursivelist[i]->m_ndata >= 0 && m_recursivelist[i]->m_ndata <= m_nMaxNumber)
        {
            if (m_recursivelist[i]->m_ndata == 0) { m_recursivelist[i]->m_pelx = m_pTopElx; }
            else for (int j = 1; j < m_grouplist.GetSize(); ++j)
                {
                    if (m_recursivelist[i]->m_ndata == ((CBracketElx *)((CListElx *)m_grouplist[j])->m_elxlist[0])->m_nnumber)
                    {
                        m_recursivelist[i]->m_pelx = m_grouplist[j];
                        break;
                    }
                }
        }
    }

    // named backref
    for (i = 0; i < m_namedbackreflist.GetSize(); ++i)
    {
        m_namedbackreflist[i]->m_nnumber = GetNamedNumber(m_namedbackreflist[i]->m_szNamed);
    }

    // named condition
    for (i = 0; i < m_namedconditionlist.GetSize(); ++i)
    {
        int nn = GetNamedNumber(m_namedconditionlist[i]->m_szNamed);

        if (nn >= 0)
        {
            m_namedconditionlist[i]->m_nnumber = nn;
            m_namedconditionlist[i]->m_pelxask = 0;
        }
    }

    return m_pTopElx;
}

template <class CHART> void CBuilderT <CHART>::Clear()
{
    for (int i = 0; i < m_objlist.GetSize(); ++i)
    {
        delete m_objlist[i];
    }

    m_objlist.Restore(0);
    m_pTopElx = 0;
    m_nMaxNumber = 0;

    memset(m_pStockElxs, 0, sizeof(m_pStockElxs));
}

//
// hex to int
//
template <class CHART> unsigned int CBuilderT <CHART>::Hex2Int(const CHART *pcsz, int length, int &used)
{
    unsigned int result = 0;
    int &i = used;

    for (i = 0; i < length; ++i)
    {
        if (pcsz[i] >= RCHART('0') && pcsz[i] <= RCHART('9'))
        { result = (result << 4) + (pcsz[i] - RCHART('0')); }
        else if (pcsz[i] >= RCHART('A') && pcsz[i] <= RCHART('F'))
        { result = (result << 4) + (0x0A + (pcsz[i] - RCHART('A'))); }
        else if (pcsz[i] >= RCHART('a') && pcsz[i] <= RCHART('f'))
        { result = (result << 4) + (0x0A + (pcsz[i] - RCHART('a'))); }
        else { break; }
    }

    return result;
}

template <class CHART> inline ElxInterface *CBuilderT <CHART>::Keep(ElxInterface *pelx)
{
    m_objlist.Push(pelx);
    return pelx;
}

template <class CHART> void CBuilderT <CHART>::MoveNext()
{
    // forwards
    prev = curr;
    curr = next;
    next = nex2;

    // get nex2
    while (!GetNext2()) {};
}

template <class CHART> int CBuilderT <CHART>::GetNext2()
{
    // check length
    if (m_nNextPos >= m_pattern.GetSize())
    {
        nex2 = CHART_INFO(0, 1, m_nNextPos, 0);
        return 1;
    }

    int   delta = 1;
    CHART ch    = m_pattern[m_nNextPos];

    // if quoted
    if (m_bQuoted)
    {
        if (ch == RCHART('\\'))
        {
            if (m_pattern[m_nNextPos + 1] == RCHART('E'))
            {
                m_quote_fun = 0;
                m_bQuoted   = 0;
                m_nNextPos += 2;
                return 0;
            }
        }

        if (m_quote_fun != 0) { nex2 = CHART_INFO((CHART)(*m_quote_fun)((int)ch), 0, m_nNextPos, delta); }
        else                  { nex2 = CHART_INFO(ch, 0, m_nNextPos, delta); }

        m_nNextPos += delta;

        return 1;
    }

    // common
    switch (ch)
    {
    case RCHART('\\'):
        {
            CHART ch1 = m_pattern[m_nNextPos + 1];

            // backref
            if (ch1 >= RCHART('0') && ch1 <= RCHART('9'))
            {
                nex2 = CHART_INFO(ch, 1, m_nNextPos, delta);
                break;
            }

            // escape
            delta     = 2;

            switch (ch1)
            {
            case RCHART('A'):
            case RCHART('Z'):
            case RCHART('z'):
            case RCHART('w'):
            case RCHART('W'):
            case RCHART('s'):
            case RCHART('S'):
            case RCHART('B'):
            case RCHART('d'):
            case RCHART('D'):
            case RCHART('k'):
            case RCHART('g'):
                nex2 = CHART_INFO(ch1, 1, m_nNextPos, delta);
                break;

            case RCHART('b'):
                if (m_nCharsetDepth > 0)
                { nex2 = CHART_INFO('\b', 0, m_nNextPos, delta); }
                else
                { nex2 = CHART_INFO(ch1, 1, m_nNextPos, delta); }

                break;

            /*
            case RCHART('<'):
            case RCHART('>'):
                if(m_nCharsetDepth > 0)
                    nex2 = CHART_INFO(ch1, 0, m_nNextPos, delta);
                else
                    nex2 = CHART_INFO(ch1, 1, m_nNextPos, delta);
                break;
            */

            case RCHART('x'):
                if (m_pattern[m_nNextPos + 2] != '{')
                {
                    int red = 0;
                    unsigned int ch2 = Hex2Int(m_pattern.GetBuffer() + m_nNextPos + 2, 2, red);

                    delta += red;

                    if (red > 0) { nex2 = CHART_INFO(RCHART(ch2), 0, m_nNextPos, delta); }
                    else         { nex2 = CHART_INFO(ch1, 0, m_nNextPos, delta); }

                    break;
                }

            case RCHART('u'):
                if (m_pattern[m_nNextPos + 2] != '{')
                {
                    int red = 0;
                    unsigned int ch2 = Hex2Int(m_pattern.GetBuffer() + m_nNextPos + 2, 4, red);

                    delta += red;

                    if (red > 0) { nex2 = CHART_INFO(RCHART(ch2), 0, m_nNextPos, delta); }
                    else         { nex2 = CHART_INFO(ch1, 0, m_nNextPos, delta); }
                }
                else
                {
                    int red = 0;
                    unsigned int ch2 = Hex2Int(m_pattern.GetBuffer() + m_nNextPos + 3, sizeof(int) * 2, red);

                    delta += red;

                    while (m_nNextPos + delta < m_pattern.GetSize() && m_pattern.At(m_nNextPos + delta) != RCHART('}'))
                    { ++delta; }

                    ++delta; // skip '}'

                    nex2 = CHART_INFO(RCHART(ch2), 0, m_nNextPos, delta);
                }

                break;

            case RCHART('a'): nex2 = CHART_INFO(RCHART('\a'), 0, m_nNextPos, delta); break;

            case RCHART('f'): nex2 = CHART_INFO(RCHART('\f'), 0, m_nNextPos, delta); break;

            case RCHART('n'): nex2 = CHART_INFO(RCHART('\n'), 0, m_nNextPos, delta); break;

            case RCHART('r'): nex2 = CHART_INFO(RCHART('\r'), 0, m_nNextPos, delta); break;

            case RCHART('t'): nex2 = CHART_INFO(RCHART('\t'), 0, m_nNextPos, delta); break;

            case RCHART('v'): nex2 = CHART_INFO(RCHART('\v'), 0, m_nNextPos, delta); break;

            case RCHART('e'): nex2 = CHART_INFO(RCHART(27), 0, m_nNextPos, delta); break;

            case RCHART('G'):  // skip '\G'
                if (m_nCharsetDepth > 0)
                {
                    m_nNextPos += 2;
                    return 0;
                }
                else
                {
                    nex2 = CHART_INFO(ch1, 1, m_nNextPos, delta);
                    break;
                }

            case RCHART('L'):
                if (!m_quote_fun) { m_quote_fun = ::tolower; }

            case RCHART('U'):
                if (!m_quote_fun) { m_quote_fun = ::toupper; }

            case RCHART('Q'):
                {
                    m_bQuoted   = 1;
                    m_nNextPos += 2;
                    return 0;
                }

            case RCHART('E'):
                {
                    m_quote_fun = 0;
                    m_bQuoted   = 0;
                    m_nNextPos += 2;
                    return 0;
                }

            case 0:
                if (m_nNextPos + 1 >= m_pattern.GetSize())
                {
                    delta = 1;
                    nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
                }
                else
                { nex2 = CHART_INFO(ch1, 0, m_nNextPos, delta); } // common '\0' char

                break;

            default:
                nex2 = CHART_INFO(ch1, 0, m_nNextPos, delta);
                break;
            }
        }
        break;

    case RCHART('*'):
    case RCHART('+'):
    case RCHART('?'):
    case RCHART('.'):
    case RCHART('{'):
    case RCHART('}'):
    case RCHART(')'):
    case RCHART('|'):
    case RCHART('$'):
        if (m_nCharsetDepth > 0) { nex2 = CHART_INFO(ch, 0, m_nNextPos, delta); }
        else                     { nex2 = CHART_INFO(ch, 1, m_nNextPos, delta); }

        break;

    case RCHART('-'):
        if (m_nCharsetDepth > 0) { nex2 = CHART_INFO(ch, 1, m_nNextPos, delta); }
        else                     { nex2 = CHART_INFO(ch, 0, m_nNextPos, delta); }

        break;

    case RCHART('('):
        {
            CHART ch1 = m_pattern[m_nNextPos + 1];
            CHART ch2 = m_pattern[m_nNextPos + 2];

            // skip remark
            if (ch1 == RCHART('?') && ch2 == RCHART('#'))
            {
                m_nNextPos += 2;

                while (m_nNextPos < m_pattern.GetSize())
                {
                    if (m_pattern[m_nNextPos] == RCHART(')')) { break; }

                    ++m_nNextPos;
                }

                if (m_pattern[m_nNextPos] == RCHART(')'))
                {
                    ++m_nNextPos;

                    // get next nex2
                    return 0;
                }
            }
            else
            {
                if (m_nCharsetDepth > 0) { nex2 = CHART_INFO(ch, 0, m_nNextPos, delta); }
                else                     { nex2 = CHART_INFO(ch, 1, m_nNextPos, delta); }
            }
        }
        break;

    case RCHART('#'):
        if (m_nFlags & EXTENDED)
        {
            // skip remark
            ++m_nNextPos;

            while (m_nNextPos < m_pattern.GetSize())
            {
                if (m_pattern[m_nNextPos] == RCHART('\n') || m_pattern[m_nNextPos] == RCHART('\r')) { break; }

                ++m_nNextPos;
            }

            // get next nex2
            return 0;
        }
        else
        {
            nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
        }

        break;

    case RCHART(' '):
    case RCHART('\f'):
    case RCHART('\n'):
    case RCHART('\r'):
    case RCHART('\t'):
    case RCHART('\v'):
        if (m_nFlags & EXTENDED)
        {
            ++m_nNextPos;

            // get next nex2
            return 0;
        }
        else
        {
            nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
        }

        break;

    case RCHART('['):
        if (m_nCharsetDepth == 0 || m_pattern.At(m_nNextPos + 1, 0) == RCHART(':'))
        {
            ++m_nCharsetDepth;
            nex2 = CHART_INFO(ch, 1, m_nNextPos, delta);
        }
        else
        {
            nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
        }

        break;

    case RCHART(']'):
        if (m_nCharsetDepth > 0)
        {
            --m_nCharsetDepth;
            nex2 = CHART_INFO(ch, 1, m_nNextPos, delta);
        }
        else
        {
            nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
        }

        break;

    case RCHART(':'):
        if (next == CHART_INFO(RCHART('['), 1)) { nex2 = CHART_INFO(ch, 1, m_nNextPos, delta); }
        else                                    { nex2 = CHART_INFO(ch, 0, m_nNextPos, delta); }

        break;

    case RCHART('^'):
        if (m_nCharsetDepth == 0 || next == CHART_INFO(RCHART('['), 1) ||
            (curr == CHART_INFO(RCHART('['), 1) && next == CHART_INFO(RCHART(':'), 1)))
        { nex2 = CHART_INFO(ch, 1, m_nNextPos, delta); }
        else
        { nex2 = CHART_INFO(ch, 0, m_nNextPos, delta); }

        break;

    case 0:
        if (m_nNextPos >= m_pattern.GetSize())
        { nex2 = CHART_INFO(ch, 1, m_nNextPos, delta); } // end of string
        else
        { nex2 = CHART_INFO(ch, 0, m_nNextPos, delta); } // common '\0' char

        break;

    default:
        nex2 = CHART_INFO(ch, 0, m_nNextPos, delta);
        break;
    }

    m_nNextPos += delta;

    return 1;
}

template <class CHART> ElxInterface *CBuilderT <CHART>::GetStockElx(int nStockId)
{
    ElxInterface **pStockElxs = m_pStockElxs;

    // check
    if (nStockId < 0 || nStockId >= STOCKELX_COUNT) { return GetStockElx(0); }

    // create if no
    if (pStockElxs[nStockId] == 0)
    {
        switch (nStockId)
        {
        case STOCKELX_EMPTY:
            pStockElxs[nStockId] = Keep(new CEmptyElx());
            break;

        case STOCKELX_WORD:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 1));

                pRange->m_ranges.Push(RCHART('A')); pRange->m_ranges.Push(RCHART('Z'));
                pRange->m_ranges.Push(RCHART('a')); pRange->m_ranges.Push(RCHART('z'));
                pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));
                pRange->m_chars .Push(RCHART('_'));

                pStockElxs[nStockId] = pRange;
            }
            break;

        case STOCKELX_WORD_NOT:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 0));

                pRange->m_ranges.Push(RCHART('A')); pRange->m_ranges.Push(RCHART('Z'));
                pRange->m_ranges.Push(RCHART('a')); pRange->m_ranges.Push(RCHART('z'));
                pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));
                pRange->m_chars .Push(RCHART('_'));

                pStockElxs[nStockId] = pRange;
            }
            break;

        case STOCKELX_DOT_ALL:
            pStockElxs[nStockId] = Keep(new CRangeElxT <CHART> (0, 0));
            break;

        case STOCKELX_DOT_NOT_ALL:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 0));

                pRange->m_chars .Push(RCHART('\n'));

                pStockElxs[nStockId] = pRange;
            }
            break;

        case STOCKELX_SPACE:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 1));

                pRange->m_chars .Push(RCHART(' '));
                pRange->m_chars .Push(RCHART('\t'));
                pRange->m_chars .Push(RCHART('\r'));
                pRange->m_chars .Push(RCHART('\n'));

                pStockElxs[nStockId] = pRange;
            }
            break;

        case STOCKELX_SPACE_NOT:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 0));

                pRange->m_chars .Push(RCHART(' '));
                pRange->m_chars .Push(RCHART('\t'));
                pRange->m_chars .Push(RCHART('\r'));
                pRange->m_chars .Push(RCHART('\n'));

                pStockElxs[nStockId] = pRange;
            }
            break;

        case STOCKELX_DIGITAL:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 1));

                pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));

                pStockElxs[nStockId] = pRange;
            }
            break;

        case STOCKELX_DIGITAL_NOT:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (0, 0));

                pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));

                pStockElxs[nStockId] = pRange;
            }
            break;

        case STOCKELX_WORD_RIGHTLEFT:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 1));

                pRange->m_ranges.Push(RCHART('A')); pRange->m_ranges.Push(RCHART('Z'));
                pRange->m_ranges.Push(RCHART('a')); pRange->m_ranges.Push(RCHART('z'));
                pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));
                pRange->m_chars .Push(RCHART('_'));

                pStockElxs[nStockId] = pRange;
            }
            break;

        case STOCKELX_WORD_RIGHTLEFT_NOT:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 0));

                pRange->m_ranges.Push(RCHART('A')); pRange->m_ranges.Push(RCHART('Z'));
                pRange->m_ranges.Push(RCHART('a')); pRange->m_ranges.Push(RCHART('z'));
                pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));
                pRange->m_chars .Push(RCHART('_'));

                pStockElxs[nStockId] = pRange;
            }
            break;

        case STOCKELX_DOT_ALL_RIGHTLEFT:
            pStockElxs[nStockId] = Keep(new CRangeElxT <CHART> (1, 0));
            break;

        case STOCKELX_DOT_NOT_ALL_RIGHTLEFT:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 0));

                pRange->m_chars .Push(RCHART('\n'));

                pStockElxs[nStockId] = pRange;
            }
            break;

        case STOCKELX_SPACE_RIGHTLEFT:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 1));

                pRange->m_chars .Push(RCHART(' '));
                pRange->m_chars .Push(RCHART('\t'));
                pRange->m_chars .Push(RCHART('\r'));
                pRange->m_chars .Push(RCHART('\n'));
                pRange->m_chars .Push(RCHART('\f'));
                pRange->m_chars .Push(RCHART('\v'));

                pStockElxs[nStockId] = pRange;
            }
            break;

        case STOCKELX_SPACE_RIGHTLEFT_NOT:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 0));

                pRange->m_chars .Push(RCHART(' '));
                pRange->m_chars .Push(RCHART('\t'));
                pRange->m_chars .Push(RCHART('\r'));
                pRange->m_chars .Push(RCHART('\n'));
                pRange->m_chars .Push(RCHART('\f'));
                pRange->m_chars .Push(RCHART('\v'));

                pStockElxs[nStockId] = pRange;
            }
            break;

        case STOCKELX_DIGITAL_RIGHTLEFT:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 1));

                pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));

                pStockElxs[nStockId] = pRange;
            }
            break;

        case STOCKELX_DIGITAL_RIGHTLEFT_NOT:
            {
                CRangeElxT <CHART> *pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (1, 0));

                pRange->m_ranges.Push(RCHART('0')); pRange->m_ranges.Push(RCHART('9'));

                pStockElxs[nStockId] = pRange;
            }
            break;
        }
    }

    // return
    return pStockElxs[nStockId];
}

template <class CHART> ElxInterface *CBuilderT <CHART>::BuildAlternative(int vaflags)
{
    if (curr == CHART_INFO(0, 1)) { return GetStockElx(STOCKELX_EMPTY); }

    // flag instance
    int flags = vaflags;

    // first part
    ElxInterface *pAlternativeOne = BuildList(flags);

    // check alternative
    if (curr == CHART_INFO(RCHART('|'), 1))
    {
        CAlternativeElx *pAlternative = (CAlternativeElx *)Keep(new CAlternativeElx());
        pAlternative->m_elxlist.Push(pAlternativeOne);

        // loop
        while (curr == CHART_INFO(RCHART('|'), 1))
        {
            // skip '|' itself
            MoveNext();

            pAlternativeOne = BuildList(flags);
            pAlternative->m_elxlist.Push(pAlternativeOne);
        }

        return pAlternative;
    }

    return pAlternativeOne;
}

template <class CHART> ElxInterface *CBuilderT <CHART>::BuildList(int &flags)
{
    if (curr == CHART_INFO(0, 1) || curr == CHART_INFO(RCHART('|'), 1) || curr == CHART_INFO(RCHART(')'), 1))
    { return GetStockElx(STOCKELX_EMPTY); }

    // first
    ElxInterface *pListOne = BuildRepeat(flags);

    if (curr != CHART_INFO(0, 1) && curr != CHART_INFO(RCHART('|'), 1) && curr != CHART_INFO(RCHART(')'), 1))
    {
        CListElx *pList = (CListElx *)Keep(new CListElx(flags & RIGHTTOLEFT));
        pList->m_elxlist.Push(pListOne);

        while (curr != CHART_INFO(0, 1) && curr != CHART_INFO(RCHART('|'), 1) && curr != CHART_INFO(RCHART(')'), 1))
        {
            pListOne = BuildRepeat(flags);

            // add
            pList->m_elxlist.Push(pListOne);
        }

        return pList;
    }

    return pListOne;
}

template <class CHART> ElxInterface *CBuilderT <CHART>::BuildRepeat(int &flags)
{
    // simple
    ElxInterface *pSimple = BuildSimple(flags);

    if (curr.type == 0) { return pSimple; }

    // is quantifier or not
    int bIsQuantifier = 1;

    // quantifier range
    unsigned int nMin = 0, nMax = 0;

    switch (curr.ch)
    {
    case RCHART('{'):
        {
            CBufferT <char> re;

            // skip '{'
            MoveNext();

            // copy
            while (curr != CHART_INFO(0, 1) && curr != CHART_INFO(RCHART('}'), 1))
            {
                re.Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
                MoveNext();
            }

            // skip '}'
            MoveNext();

            // read
            int red;
            char *str = re.GetBuffer();

            if (!ReadDec(str, nMin)) { red = 0; }
            else  if (*str != ',')   { red = 1; }
            else
            {
                ++str;

                if (!ReadDec(str, nMax)) { red = 2; }
                else                     { red = 3; }
            }

            // check
            if (red  <=  1)  { nMax = nMin; }

            if (red  ==  2)  { nMax = INT_MAX; }

            if (nMax < nMin) { nMax = nMin; }
        }
        break;

    case RCHART('?'):
        nMin = 0;
        nMax = 1;

        // skip '?'
        MoveNext();
        break;

    case RCHART('*'):
        nMin = 0;
        nMax = INT_MAX;

        // skip '*'
        MoveNext();
        break;

    case RCHART('+'):
        nMin = 1;
        nMax = INT_MAX;

        // skip '+'
        MoveNext();
        break;

    default:
        bIsQuantifier = 0;
        break;
    }

    // do quantify
    if (bIsQuantifier)
    {
        // 0 times
        if (nMax == 0) { return GetStockElx(STOCKELX_EMPTY); }

        // fixed times
        if (nMin == nMax)
        {
            if (curr == CHART_INFO(RCHART('?'), 1) || curr == CHART_INFO(RCHART('+'), 1)) { MoveNext(); }

            return Keep(new CRepeatElx(pSimple, nMin));
        }

        // range times
        if (curr == CHART_INFO(RCHART('?'), 1))
        {
            MoveNext();
            return Keep(new CReluctantElx(pSimple, nMin, nMax));
        }
        else if (curr == CHART_INFO(RCHART('+'), 1))
        {
            MoveNext();
            return Keep(new CPossessiveElx(pSimple, nMin, nMax));
        }
        else
        {
            return Keep(new CGreedyElx(pSimple, nMin, nMax));
        }
    }

    return pSimple;
}

template <class CHART> ElxInterface *CBuilderT <CHART>::BuildSimple(int &flags)
{
    CBufferT <CHART> fixed;

    while (curr != CHART_INFO(0, 1))
    {
        if (curr.type == 0)
        {
            if (next == CHART_INFO(RCHART('{'), 1) || next == CHART_INFO(RCHART('?'), 1) ||
                next == CHART_INFO(RCHART('*'), 1) || next == CHART_INFO(RCHART('+'), 1))
            {
                if (fixed.GetSize() == 0)
                {
                    fixed.Append(curr.ch, 1);
                    MoveNext();
                }

                break;
            }
            else
            {
                fixed.Append(curr.ch, 1);
                MoveNext();
            }
        }
        else if (curr.type == 1)
        {
            CHART vch = curr.ch;

            // end of simple
            if (vch == RCHART(')') || vch == RCHART('|')) { break; }

            // has fixed already
            if (fixed.GetSize() > 0) { break; }

            // left parentheses
            if (vch == RCHART('(')) { return BuildRecursive(flags); }

            // char set
            if (vch == RCHART('[') || vch == RCHART('.') || vch == RCHART('w') || vch == RCHART('W') ||
                vch == RCHART('s') || vch == RCHART('S') || vch == RCHART('d') || vch == RCHART('D')
               )
            {
                return BuildCharset(flags);
            }

            // boundary
            if (vch == RCHART('^') || vch == RCHART('$') || vch == RCHART('A') || vch == RCHART('Z') ||
                vch == RCHART('z') ||
                vch == RCHART('b') || vch == RCHART('B') || vch == RCHART('G') // vch == RCHART('<') || vch == RCHART('>')
               )
            {
                return BuildBoundary(flags);
            }

            // backref
            if (vch == RCHART('\\') || vch == RCHART('k') || vch == RCHART('g'))
            {
                return BuildBackref(flags);
            }

            // treat vchar as char
            fixed.Append(curr.ch, 1);
            MoveNext();
        }
    }

    if (fixed.GetSize() > 0)
    { return Keep(new CStringElxT <CHART> (fixed.GetBuffer(), fixed.GetSize(), flags & RIGHTTOLEFT, flags & IGNORECASE)); }
    else
    { return GetStockElx(STOCKELX_EMPTY); }
}

#define max(a, b)  (((a) > (b)) ? (a) : (b))
#define min(a, b)  (((a) < (b)) ? (a) : (b))

template <class CHART> ElxInterface *CBuilderT <CHART>::BuildCharset(int &flags)
{
    // char
    CHART ch = curr.ch;

    // skip
    MoveNext();

    switch (ch)
    {
    case RCHART('.'):
        return GetStockElx(
                   flags & RIGHTTOLEFT ?
                   ((flags & SINGLELINE) ? STOCKELX_DOT_ALL_RIGHTLEFT : STOCKELX_DOT_NOT_ALL_RIGHTLEFT) :
                   ((flags & SINGLELINE) ? STOCKELX_DOT_ALL : STOCKELX_DOT_NOT_ALL)
               );

    case RCHART('w'):
        return GetStockElx(flags & RIGHTTOLEFT ? STOCKELX_WORD_RIGHTLEFT : STOCKELX_WORD);

    case RCHART('W'):
        return GetStockElx(flags & RIGHTTOLEFT ? STOCKELX_WORD_RIGHTLEFT_NOT : STOCKELX_WORD_NOT);

    case RCHART('s'):
        return GetStockElx(flags & RIGHTTOLEFT ? STOCKELX_SPACE_RIGHTLEFT : STOCKELX_SPACE);

    case RCHART('S'):
        return GetStockElx(flags & RIGHTTOLEFT ? STOCKELX_SPACE_RIGHTLEFT_NOT : STOCKELX_SPACE_NOT);

    case RCHART('d'):
        return GetStockElx(flags & RIGHTTOLEFT ? STOCKELX_DIGITAL_RIGHTLEFT : STOCKELX_DIGITAL);

    case RCHART('D'):
        return GetStockElx(flags & RIGHTTOLEFT ? STOCKELX_DIGITAL_RIGHTLEFT_NOT : STOCKELX_DIGITAL_NOT);

    case RCHART('['):
        {
            CRangeElxT <CHART> *pRange;

            // create
            if (curr == CHART_INFO(RCHART(':'), 1))
            {
                CBufferT <char> posix;

                do
                {
                    posix.Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
                    MoveNext();
                } while (curr.ch != RCHART(0) && curr != CHART_INFO(RCHART(']'), 1));

                MoveNext(); // skip ']'

                // posix
                return Keep(new CPosixElxT <CHART> (posix.GetBuffer(), flags & RIGHTTOLEFT));
            }
            else if (curr == CHART_INFO(RCHART('^'), 1))
            {
                MoveNext(); // skip '^'
                pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (flags & RIGHTTOLEFT, 0));
            }
            else
            {
                pRange = (CRangeElxT <CHART> *)Keep(new CRangeElxT <CHART> (flags & RIGHTTOLEFT, 1));
            }

            // parse
            while (curr != CHART_INFO(0, 1) && curr != CHART_INFO(RCHART(']'), 1))
            {
                ch = curr.ch;

                if (curr.type == 1 && (
                        ch == RCHART('.') || ch == RCHART('w') || ch == RCHART('W') || ch == RCHART('s') || ch == RCHART('S') ||
                        ch == RCHART('d') || ch == RCHART('D') ||
                        (ch == RCHART('[') && next == CHART_INFO(RCHART(':'), 1))
                    ))
                {
                    pRange->m_embeds.Push(BuildCharset(flags));
                }
                else if (next == CHART_INFO(RCHART('-'), 1) && nex2.type == 0)
                {
                    pRange->m_ranges.Push(ch); pRange->m_ranges.Push(nex2.ch);

                    // next
                    MoveNext();
                    MoveNext();
                    MoveNext();
                }
                else
                {
                    pRange->m_chars.Push(ch);

                    // next
                    MoveNext();
                }
            }

            // skip ']'
            MoveNext();

            if (flags & IGNORECASE)
            {
                CBufferT <CHART> &ranges = pRange->m_ranges;
                int i, oldcount = ranges.GetSize() / 2;

                for (i = 0; i < oldcount; ++i)
                {
                    CHART newmin, newmax;

                    if (ranges[i * 2] <= RCHART('Z') && ranges[i * 2 + 1] >= RCHART('A'))
                    {
                        newmin = tolower(max(RCHART('A'), ranges[i * 2  ]));
                        newmax = tolower(min(RCHART('Z'), ranges[i * 2 + 1]));

                        if (newmin < ranges[i * 2] || newmax > ranges[i * 2 + 1])
                        {
                            ranges.Push(newmin);
                            ranges.Push(newmax);
                        }
                    }

                    if (ranges[i * 2] <= RCHART('z') && ranges[i * 2 + 1] >= RCHART('a'))
                    {
                        newmin = toupper(max(RCHART('a'), ranges[i * 2  ]));
                        newmax = toupper(min(RCHART('z'), ranges[i * 2 + 1]));

                        if (newmin < ranges[i * 2] || newmax > ranges[i * 2 + 1])
                        {
                            ranges.Push(newmin);
                            ranges.Push(newmax);
                        }
                    }
                }

                CBufferT <CHART> &chars = pRange->m_chars;
                oldcount = chars.GetSize();

                for (i = 0; i < oldcount; ++i)
                {
                    if (isupper(chars[i]) && !pRange->IsContainChar(tolower(chars[i])))
                    { chars.Push(tolower(chars[i])); }

                    if (islower(chars[i]) && !pRange->IsContainChar(toupper(chars[i])))
                    { chars.Push(toupper(chars[i])); }
                }
            }

            return pRange;
        }
    }

    return GetStockElx(STOCKELX_EMPTY);
}

template <class CHART> ElxInterface *CBuilderT <CHART>::BuildRecursive(int &flags)
{
    // skip '('
    MoveNext();

    if (curr == CHART_INFO(RCHART('?'), 1))
    {
        ElxInterface *pElx = 0;

        // skip '?'
        MoveNext();

        int bNegative = 0;
        CHART named_end = RCHART('>');

        switch (curr.ch)
        {
        case RCHART('!'):
            bNegative = 1;

        case RCHART('='):
            {
                MoveNext(); // skip '!' or '='
                pElx = Keep(new CAssertElx(BuildAlternative(flags & ~RIGHTTOLEFT), !bNegative));
            }
            break;

        case RCHART('<'):
            switch (next.ch)
            {
            case RCHART('!'):
                bNegative = 1;

            case RCHART('='):
                MoveNext(); // skip '<'
                MoveNext(); // skip '!' or '='
                {
                    pElx = Keep(new CAssertElx(BuildAlternative(flags | RIGHTTOLEFT), !bNegative));
                }
                break;

            default: // named group
                break;
            }

            // break if assertion // else named
            if (pElx != 0) { break; }

        case RCHART('P'):
            if (curr.ch == RCHART('P')) { MoveNext(); } // skip 'P'

        case RCHART('\''):
            if (curr.ch == RCHART('<')) { named_end = RCHART('>'); }
            else if (curr.ch == RCHART('\'')) { named_end = RCHART('\''); }

            MoveNext(); // skip '<' or '\''
            {
                // named number
                int nThisBackref = m_nNextNamed ++;

                CListElx     *pList  = (CListElx *)Keep(new CListElx(flags & RIGHTTOLEFT));
                CBracketElx *pleft  = (CBracketElx *)Keep(new CBracketElx(-1, flags & RIGHTTOLEFT ? 1 : 0));
                CBracketElx *pright = (CBracketElx *)Keep(new CBracketElx(-1, flags & RIGHTTOLEFT ? 0 : 1));

                // save name
                CBufferT <CHART> &name = pleft->m_szNamed;
                CBufferT <char> num;

                while (curr.ch != RCHART(0) && curr.ch != named_end)
                {
                    name.Append(curr.ch, 1);
                    num .Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
                    MoveNext();
                }

                MoveNext(); // skip '>' or '\''

                // check <num>
                unsigned int number;
                char *str = num.GetBuffer();

                if (ReadDec(str, number) ? (*str == '\0') : 0)
                {
                    pleft ->m_nnumber = number;
                    pright->m_nnumber = number;

                    name.Release();
                }

                // left, center, right
                pList->m_elxlist.Push(pleft);
                pList->m_elxlist.Push(BuildAlternative(flags));
                pList->m_elxlist.Push(pright);

                // for recursive
                m_namedlist.Prepare(nThisBackref);
                m_namedlist[nThisBackref] = pList;

                pElx = pList;
            }
            break;

        case RCHART('>'):
            {
                MoveNext(); // skip '>'
                pElx = Keep(new CIndependentElx(BuildAlternative(flags)));
            }
            break;

        case RCHART('R'):
            MoveNext(); // skip 'R'

            while (curr.ch != RCHART(0) && isspace(curr.ch)) { MoveNext(); } // skip space

            if (curr.ch == RCHART('<') || curr.ch == RCHART('\''))
            {
                named_end = curr.ch == RCHART('<') ? RCHART('>') : RCHART('\'');
                CDelegateElx *pDelegate = (CDelegateElx *)Keep(new CDelegateElx(-3));

                MoveNext(); // skip '<' or '\\'

                // save name
                CBufferT <CHART> &name = pDelegate->m_szNamed;
                CBufferT <char> num;

                while (curr.ch != RCHART(0) && curr.ch != named_end)
                {
                    name.Append(curr.ch, 1);
                    num .Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
                    MoveNext();
                }

                MoveNext(); // skip '>' or '\''

                // check <num>
                unsigned int number;
                char *str = num.GetBuffer();

                if (ReadDec(str, number) ? (*str == '\0') : 0)
                {
                    pDelegate->m_ndata = number;
                    name.Release();
                }

                m_recursivelist.Push(pDelegate);
                pElx = pDelegate;
            }
            else
            {
                CBufferT <char> rto;

                while (curr.ch != RCHART(0) && curr.ch != RCHART(')'))
                {
                    rto.Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
                    MoveNext();
                }

                unsigned int rtono = 0;
                char *str = rto.GetBuffer();
                ReadDec(str, rtono);

                CDelegateElx *pDelegate = (CDelegateElx *)Keep(new CDelegateElx(rtono));

                m_recursivelist.Push(pDelegate);
                pElx = pDelegate;
            }

            break;

        case RCHART('('):
            {
                CConditionElx *pConditionElx = (CConditionElx *)Keep(new CConditionElx());

                // condition
                ElxInterface *&pCondition = pConditionElx->m_pelxask;

                if (next == CHART_INFO(RCHART('?'), 1))
                {
                    pCondition = BuildRecursive(flags);
                }
                else // named, assert or number
                {
                    MoveNext(); // skip '('
                    int pos0 = curr.pos;

                    // save elx condition
                    pCondition = Keep(new CAssertElx(BuildAlternative(flags), 1));

                    // save name
                    pConditionElx->m_szNamed.Append(m_pattern.GetBuffer() + pos0, curr.pos - pos0, 1);

                    // save number
                    CBufferT <char> numstr;

                    while (pos0 < curr.pos)
                    {
                        CHART ch = m_pattern[pos0];
                        numstr.Append(((ch & (CHART)0xff) == ch) ? (char)ch : 0, 1);
                        ++pos0;
                    }

                    unsigned int number;
                    char *str = numstr.GetBuffer();

                    // valid group number
                    if (ReadDec(str, number) ? (*str == '\0') : 0)
                    {
                        pConditionElx->m_nnumber = number;
                        pCondition = 0;
                    }
                    else // maybe elx, maybe named
                    {
                        pConditionElx->m_nnumber = -1;
                        m_namedconditionlist.Push(pConditionElx);
                    }

                    MoveNext(); // skip ')'
                }

                // alternative
                {
                    int newflags = flags;

                    pConditionElx->m_pelxyes = BuildList(newflags);
                }

                if (curr.ch == RCHART('|'))
                {
                    MoveNext(); // skip '|'

                    pConditionElx->m_pelxno = BuildAlternative(flags);
                }
                else
                {
                    pConditionElx->m_pelxno = 0;
                }

                pElx = pConditionElx;
            }
            break;

        default:
            while (curr.ch != RCHART(0) && isspace(curr.ch)) { MoveNext(); } // skip space

            if (curr.ch >= RCHART('0') && curr.ch <= RCHART('9')) // recursive (?1) => (?R1)
            {
                CBufferT <char> rto;

                while (curr.ch != RCHART(0) && curr.ch != RCHART(')'))
                {
                    rto.Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
                    MoveNext();
                }

                unsigned int rtono = 0;
                char *str = rto.GetBuffer();
                ReadDec(str, rtono);

                CDelegateElx *pDelegate = (CDelegateElx *)Keep(new CDelegateElx(rtono));

                m_recursivelist.Push(pDelegate);
                pElx = pDelegate;
            }
            else
            {
                // flag
                int newflags = flags;

                while (curr != CHART_INFO(0, 1) && curr.ch != RCHART(':') && curr.ch != RCHART(')') &&
                       curr != CHART_INFO(RCHART('('), 1))
                {
                    int tochange = 0;

                    switch (curr.ch)
                    {
                    case RCHART('i'):
                    case RCHART('I'):
                        tochange = IGNORECASE;
                        break;

                    case RCHART('s'):
                    case RCHART('S'):
                        tochange = SINGLELINE;
                        break;

                    case RCHART('m'):
                    case RCHART('M'):
                        tochange = MULTILINE;
                        break;

                    case RCHART('g'):
                    case RCHART('G'):
                        tochange = GLOBAL;
                        break;

                    case RCHART('-'):
                        bNegative = 1;
                        break;
                    }

                    if (bNegative) { newflags &= ~tochange; }
                    else           { newflags |=  tochange; }

                    // move to next char
                    MoveNext();
                }

                if (curr.ch == RCHART(':') || curr == CHART_INFO(RCHART('('), 1))
                {
                    // skip ':'
                    if (curr.ch == RCHART(':')) { MoveNext(); }

                    pElx = BuildAlternative(newflags);
                }
                else
                {
                    // change parent flags
                    flags = newflags;

                    pElx = GetStockElx(STOCKELX_EMPTY);
                }
            }

            break;
        }

        MoveNext(); // skip ')'

        return pElx;
    }
    else
    {
        // group and number
        CListElx *pList = (CListElx *)Keep(new CListElx(flags & RIGHTTOLEFT));
        int nThisBackref = ++ m_nMaxNumber;

        // left, center, right
        pList->m_elxlist.Push(Keep(new CBracketElx(nThisBackref, flags & RIGHTTOLEFT ? 1 : 0)));
        pList->m_elxlist.Push(BuildAlternative(flags));
        pList->m_elxlist.Push(Keep(new CBracketElx(nThisBackref, flags & RIGHTTOLEFT ? 0 : 1)));

        // for recursive
        m_grouplist.Prepare(nThisBackref);
        m_grouplist[nThisBackref] = pList;

        // right
        MoveNext(); // skip ')'

        return pList;
    }
}

template <class CHART> ElxInterface *CBuilderT <CHART>::BuildBoundary(int &flags)
{
    // char
    CHART ch = curr.ch;

    // skip
    MoveNext();

    switch (ch)
    {
    case RCHART('^'):
        return Keep(new CBoundaryElxT <CHART> ((flags & MULTILINE) ? BOUNDARY_LINE_BEGIN : BOUNDARY_FILE_BEGIN));

    case RCHART('$'):
        return Keep(new CBoundaryElxT <CHART> ((flags & MULTILINE) ? BOUNDARY_LINE_END : BOUNDARY_FILE_END));

    case RCHART('b'):
        return Keep(new CBoundaryElxT <CHART> (BOUNDARY_WORD_EDGE));

    case RCHART('B'):
        return Keep(new CBoundaryElxT <CHART> (BOUNDARY_WORD_EDGE, 0));

    case RCHART('A'):
        return Keep(new CBoundaryElxT <CHART> (BOUNDARY_FILE_BEGIN));

    case RCHART('Z'):
        return Keep(new CBoundaryElxT <CHART> (BOUNDARY_FILE_END_N));

    case RCHART('z'):
        return Keep(new CBoundaryElxT <CHART> (BOUNDARY_FILE_END));

    case RCHART('G'):
        if (flags & GLOBAL) { return Keep(new CGlobalElx()); }
        else                { return GetStockElx(STOCKELX_EMPTY); }

    default:
        return GetStockElx(STOCKELX_EMPTY);
    }
}

template <class CHART> ElxInterface *CBuilderT <CHART>::BuildBackref(int &flags)
{
    // skip '\\' or '\k' or '\g'
    MoveNext();

    if (curr.ch == RCHART('<') || curr.ch == RCHART('\''))
    {
        CHART named_end = curr.ch == RCHART('<') ? RCHART('>') : RCHART('\'');
        CBackrefElxT <CHART> *pbackref = (CBackrefElxT <CHART> *)Keep(new CBackrefElxT <CHART> (-1,
                                         flags & RIGHTTOLEFT, flags & IGNORECASE));

        MoveNext(); // skip '<' or '\''

        // save name
        CBufferT <CHART> &name = pbackref->m_szNamed;
        CBufferT <char> num;

        while (curr.ch != RCHART(0) && curr.ch != named_end)
        {
            name.Append(curr.ch, 1);
            num .Append(((curr.ch & (CHART)0xff) == curr.ch) ? (char)curr.ch : 0, 1);
            MoveNext();
        }

        MoveNext(); // skip '>' or '\''

        // check <num>
        unsigned int number;
        char *str = num.GetBuffer();

        if (ReadDec(str, number) ? (*str == '\0') : 0)
        {
            pbackref->m_nnumber = number;
            name.Release();
        }
        else
        {
            m_namedbackreflist.Push(pbackref);
        }

        return pbackref;
    }
    else
    {
        unsigned int nbackref = 0;

        for (int i = 0; i < 3; ++i)
        {
            if (curr.ch >= RCHART('0') && curr.ch <= RCHART('9'))
            { nbackref = nbackref * 10 + (curr.ch - RCHART('0')); }
            else
            { break; }

            MoveNext();
        }

        return Keep(new CBackrefElxT <CHART> (nbackref, flags & RIGHTTOLEFT, flags & IGNORECASE));
    }
}

template <class CHART> int CBuilderT <CHART>::ReadDec(char *&str, unsigned int &dec)
{
    int s = 0;

    while (str[s] != 0 && isspace(str[s])) { ++s; }

    if (str[s] < '0' || str[s] > '9') { return 0; }

    dec = 0;
    unsigned int i;

    for (i = s; i < sizeof(CHART) * 3 + s; ++i)
    {
        if (str[i] >= '0' && str[i] <= '9') { dec = dec * 10 + (str[i] - '0'); }
        else                                { break; }
    }

    while (str[i] != 0 && isspace(str[i])) { ++i; }

    str += i;

    return 1;
}

//
// Regexp
//
template <class CHART> class CRegexpT
{
public:
    CRegexpT(const CHART *pattern = 0, int flags = 0);
    CRegexpT(const CHART *pattern, int length, int flags);
    void Compile(const CHART *pattern, int flags = 0);
    void Compile(const CHART *pattern, int length, int flags);

public:
    MatchResult MatchExact(const CHART *tstring, CContext *pContext = 0) const;
    MatchResult MatchExact(const CHART *tstring, int length, CContext *pContext = 0) const;
    MatchResult Match(const CHART *tstring, int start = -1, CContext *pContext = 0) const;
    MatchResult Match(const CHART *tstring, int length, int start, CContext *pContext = 0) const;
    MatchResult Match(CContext *pContext) const;
    CContext *PrepareMatch(const CHART *tstring, int start = -1, CContext *pContext = 0) const;
    CContext *PrepareMatch(const CHART *tstring, int length, int start, CContext *pContext = 0) const;
    CHART *Replace(const CHART *tstring, const CHART *replaceto, int start = -1, int ntimes = -1,
                   MatchResult *result = 0, CContext *pContext = 0) const;
    CHART *Replace(const CHART *tstring, int string_length, const CHART *replaceto, int to_length,
                   int &result_length, int start = -1, int ntimes = -1, MatchResult *result = 0, CContext *pContext = 0) const;
    int GetNamedGroupNumber(const CHART *group_name) const;

public:
    static void ReleaseString(CHART     *tstring);
    static void ReleaseContext(CContext *pContext);

public:
    CBuilderT <CHART> m_builder;
};

//
// Implementation
//
template <class CHART> CRegexpT <CHART>::CRegexpT(const CHART *pattern, int flags)
{
    Compile(pattern, CBufferRefT<CHART>(pattern).GetSize(), flags);
}

template <class CHART> CRegexpT <CHART>::CRegexpT(const CHART *pattern, int length, int flags)
{
    Compile(pattern, length, flags);
}

template <class CHART> inline void CRegexpT <CHART>::Compile(const CHART *pattern, int flags)
{
    Compile(pattern, CBufferRefT<CHART>(pattern).GetSize(), flags);
}

template <class CHART> void CRegexpT <CHART>::Compile(const CHART *pattern, int length, int flags)
{
    m_builder.Clear();

    if (pattern != 0) { m_builder.Build(CBufferRefT<CHART>(pattern, length), flags); }
}

template <class CHART> inline MatchResult CRegexpT <CHART>::MatchExact(const CHART *tstring,
        CContext *pContext) const
{
    return MatchExact(tstring, CBufferRefT<CHART>(tstring).GetSize(), pContext);
}

template <class CHART> MatchResult CRegexpT <CHART>::MatchExact(const CHART *tstring, int length,
        CContext  *pContext) const
{
    if (m_builder.m_pTopElx == 0) { return 0; }

    // info
    int endpos = 0;

    CContext context;

    if (pContext == 0) { pContext = &context; }

    pContext->m_stack.Restore(0);
    pContext->m_capturestack.Restore(0);
    pContext->m_captureindex.Restore(0);

    pContext->m_nParenZindex  = 0;
    pContext->m_nLastBeginPos = -1;
    pContext->m_pMatchString  = (void *)tstring;
    pContext->m_pMatchStringLength = length;

    if (m_builder.m_nFlags & RIGHTTOLEFT)
    {
        pContext->m_nBeginPos   = length;
        pContext->m_nCurrentPos = length;
        endpos = 0;
    }
    else
    {
        pContext->m_nBeginPos   = 0;
        pContext->m_nCurrentPos = 0;
        endpos = length;
    }

    pContext->m_captureindex.Prepare(m_builder.m_nMaxNumber, -1);
    pContext->m_captureindex[0] = 0;
    pContext->m_capturestack.Push(0);
    pContext->m_capturestack.Push(pContext->m_nCurrentPos);
    pContext->m_capturestack.Push(-1);
    pContext->m_capturestack.Push(-1);

    // match
    if (!m_builder.m_pTopElx->Match(pContext)) { return 0; }
    else
    {
        while (pContext->m_nCurrentPos != endpos)
        {
            if (!m_builder.m_pTopElx->MatchNext(pContext)) { return 0; }
            else
            {
                if (pContext->m_nLastBeginPos == pContext->m_nBeginPos &&
                    pContext->m_nBeginPos == pContext->m_nCurrentPos)
                { return 0; }
                else
                { pContext->m_nLastBeginPos = pContext->m_nCurrentPos; }
            }
        }

        // end pos
        pContext->m_capturestack[2] = pContext->m_nCurrentPos;

        return MatchResult(pContext, m_builder.m_nMaxNumber);
    }
}

template <class CHART> MatchResult CRegexpT <CHART>::Match(const CHART *tstring, int start,
                                                           CContext *pContext) const
{
    return Match(tstring, CBufferRefT<CHART>(tstring).GetSize(), start, pContext);
}

template <class CHART> MatchResult CRegexpT <CHART>::Match(const CHART *tstring, int length, int start,
                                                           CContext *pContext) const
{
    if (m_builder.m_pTopElx == 0) { return 0; }

    CContext context;

    if (pContext == 0) { pContext = &context; }

    PrepareMatch(tstring, length, start, pContext);

    return Match(pContext);
}

template <class CHART> MatchResult CRegexpT <CHART>::Match(CContext *pContext) const
{
    if (m_builder.m_pTopElx == 0 || pContext == NULL) { return 0; }

    int endpos, delta;

    if (m_builder.m_nFlags & RIGHTTOLEFT)
    {
        endpos = -1;
        delta  = -1;
    }
    else
    {
        endpos = pContext->m_pMatchStringLength + 1;
        delta  = 1;
    }

    while (pContext->m_nCurrentPos != endpos)
    {
        pContext->m_captureindex.Restore(0);
        pContext->m_stack       .Restore(0);
        pContext->m_capturestack.Restore(0);

        pContext->m_captureindex.Prepare(m_builder.m_nMaxNumber, -1);
        pContext->m_captureindex[0] = 0;
        pContext->m_capturestack.Push(0);
        pContext->m_capturestack.Push(pContext->m_nCurrentPos);
        pContext->m_capturestack.Push(-1);
        pContext->m_capturestack.Push(-1);

        if (m_builder.m_pTopElx->Match(pContext))
        {
            pContext->m_capturestack[2] = pContext->m_nCurrentPos;

            // zero width
            if (pContext->m_capturestack[1] == pContext->m_nCurrentPos)
            {
                pContext->m_nCurrentPos += delta;
            }

            // save pos
            pContext->m_nLastBeginPos   = pContext->m_nBeginPos;
            pContext->m_nBeginPos       = pContext->m_nCurrentPos;

            // return
            return MatchResult(pContext, m_builder.m_nMaxNumber);
        }
        else
        {
            pContext->m_nCurrentPos += delta;
        }
    }

    return 0;
}

template <class CHART> inline CContext *CRegexpT <CHART>::PrepareMatch(const CHART *tstring, int start,
        CContext *pContext) const
{
    return PrepareMatch(tstring, CBufferRefT<CHART>(tstring).GetSize(), start, pContext);
}

template <class CHART> CContext *CRegexpT <CHART>::PrepareMatch(const CHART *tstring, int length, int start,
        CContext *pContext) const
{
    if (m_builder.m_pTopElx == 0) { return 0; }

    if (pContext == 0) { pContext = new CContext(); }

    pContext->m_nParenZindex  =  0;
    pContext->m_nLastBeginPos = -1;
    pContext->m_pMatchString  = (void *)tstring;
    pContext->m_pMatchStringLength = length;

    if (start < 0)
    {
        if (m_builder.m_nFlags & RIGHTTOLEFT)
        {
            pContext->m_nBeginPos   = length;
            pContext->m_nCurrentPos = length;
        }
        else
        {
            pContext->m_nBeginPos   = 0;
            pContext->m_nCurrentPos = 0;
        }
    }
    else
    {
        if (start > length) { start = length + ((m_builder.m_nFlags & RIGHTTOLEFT) ? 0 : 1); }

        pContext->m_nBeginPos   = start;
        pContext->m_nCurrentPos = start;
    }

    return pContext;
}

template <class CHART> inline int CRegexpT <CHART>::GetNamedGroupNumber(const CHART *group_name) const
{
    return m_builder.GetNamedNumber(group_name);
}

template <class CHART>
CHART *CRegexpT<CHART>::Replace(const CHART *tstring, const CHART *replaceto, int start, int ntimes,
                                MatchResult *result, CContext *pContext) const
{
    int result_length = 0;
    return Replace(tstring, CBufferRefT<CHART>(tstring).GetSize(), replaceto,
                   CBufferRefT<CHART>(replaceto).GetSize(), result_length, start, ntimes, result, pContext);
}

template <class CHART>
CHART *CRegexpT<CHART>::Replace(const CHART *tstring, int string_length, const CHART *replaceto,
                                int to_length, int &result_length, int start, int ntimes, MatchResult *remote_result,
                                CContext *oContext) const

{
    if (m_builder.m_pTopElx == 0) { return 0; }

    // --- compile replace to ---

    CBufferT <int> compiledto;

    static const CHART rtoptn[] = { RCHART('\\'), RCHART('$'), RCHART('('), RCHART('?'), RCHART(':'),
                                    RCHART('['), RCHART('$'), RCHART('&'), RCHART('`'), RCHART('\''), RCHART('+'), RCHART('_'),
                                    RCHART('\\'), RCHART('d'), RCHART(']'), RCHART('|'), RCHART('\\'), RCHART('{'), RCHART('.'),
                                    RCHART('*'), RCHART('?'), RCHART('\\'), RCHART('}'), RCHART(')'), RCHART('\0')
                                  };
    static CRegexpT <CHART> rtoreg(rtoptn);

    MatchResult local_result(0), * result = remote_result ? remote_result : & local_result;

    // prepare
    CContext *pContext = rtoreg.PrepareMatch(replaceto, to_length, -1, oContext);
    int lastIndex = 0, nmatch = 0;

    while (((*result) = rtoreg.Match(pContext)).IsMatched())
    {
        int delta = result->GetStart() - lastIndex;

        if (delta > 0)
        {
            compiledto.Push(lastIndex);
            compiledto.Push(delta);
        }

        lastIndex = result->GetStart();
        delta     = 2;

        switch (replaceto[lastIndex + 1])
        {
        case RCHART('$'):
            compiledto.Push(lastIndex);
            compiledto.Push(1);
            break;

        case RCHART('&'):
        case RCHART('`'):
        case RCHART('\''):
        case RCHART('+'):
        case RCHART('_'):
            compiledto.Push(-1);
            compiledto.Push((int)replaceto[lastIndex + 1]);
            break;

        case RCHART('{'):
            delta  = result->GetEnd() - result->GetStart();
            nmatch = m_builder.GetNamedNumber(CBufferRefT <CHART> (replaceto + (lastIndex + 2), delta - 3));

            if (nmatch > 0 && nmatch <= m_builder.m_nMaxNumber)
            {
                compiledto.Push(-2);
                compiledto.Push(nmatch);
            }
            else
            {
                compiledto.Push(lastIndex);
                compiledto.Push(delta);
            }

            break;

        default:
            nmatch = 0;

            for (delta = 1; delta <= 3; ++delta)
            {
                CHART ch = replaceto[lastIndex + delta];

                if (ch < RCHART('0') || ch > RCHART('9')) { break; }

                nmatch = nmatch * 10 + (ch - RCHART('0'));
            }

            if (nmatch > m_builder.m_nMaxNumber)
            {
                while (nmatch > m_builder.m_nMaxNumber)
                {
                    nmatch /= 10;
                    --delta;
                }

                if (nmatch == 0)
                {
                    delta = 1;
                }
            }

            if (delta == 1)
            {
                compiledto.Push(lastIndex);
                compiledto.Push(1);
            }
            else
            {
                compiledto.Push(-2);
                compiledto.Push(nmatch);
            }

            break;
        }

        lastIndex += delta;
    }

    if (lastIndex < to_length)
    {
        compiledto.Push(lastIndex);
        compiledto.Push(to_length - lastIndex);
    }

    int rightleft = m_builder.m_nFlags & RIGHTTOLEFT;

    int tb = rightleft ? compiledto.GetSize() - 2 : 0;
    int te = rightleft ? -2 : compiledto.GetSize();
    int ts = rightleft ? -2 : 2;

    // --- compile complete ---

    int beginpos  = rightleft ? string_length : 0;
    int endpos    = rightleft ? 0 : string_length;

    int toIndex0  = 0;
    int toIndex1  = 0;
    int i, ntime;

    CBufferT <const CHART *> buffer;

    // prepare
    pContext  = PrepareMatch(tstring, string_length, start, pContext);
    lastIndex = beginpos;

    // Match
    for (ntime = 0; ntimes < 0 || ntime < ntimes; ++ntime)
    {
        (*result) = Match(pContext);

        if (!result->IsMatched()) { break; }

        // before
        if (rightleft)
        {
            int distance = lastIndex - result->GetEnd();

            if (distance)
            {
                buffer.Push(tstring + result->GetEnd());
                buffer.Push((const CHART *)distance);

                toIndex1 -= distance;
            }

            lastIndex = result->GetStart();
        }
        else
        {
            int distance = result->GetStart() - lastIndex;

            if (distance)
            {
                buffer.Push(tstring + lastIndex);
                buffer.Push((const CHART *)distance);

                toIndex1 += distance;
            }

            lastIndex = result->GetEnd();
        }

        toIndex0 = toIndex1;

        // middle
        for (i = tb; i != te; i += ts)
        {
            int off = compiledto[i];
            int len = compiledto[i + 1];

            const CHART *sub = replaceto + off;

            if (off == -1)
            {
                switch (RCHART(len))
                {
                case RCHART('&'):
                    sub = tstring + result->GetStart();
                    len = result->GetEnd() - result->GetStart();
                    break;

                case RCHART('`'):
                    sub = tstring;
                    len = result->GetStart();
                    break;

                case RCHART('\''):
                    sub = tstring + result->GetEnd();
                    len = string_length - result->GetEnd();
                    break;

                case RCHART('+'):
                    for (nmatch = result->MaxGroupNumber(); nmatch >= 0; --nmatch)
                    {
                        if (result->GetGroupStart(nmatch) >= 0) { break; }
                    }

                    sub = tstring + result->GetGroupStart(nmatch);
                    len = result->GetGroupEnd(nmatch) - result->GetGroupStart(nmatch);
                    break;

                case RCHART('_'):
                    sub = tstring;
                    len = string_length;
                    break;
                }
            }
            else if (off == -2)
            {
                sub = tstring + result->GetGroupStart(len);
                len = result->GetGroupEnd(len) - result->GetGroupStart(len);
            }

            buffer.Push(sub);
            buffer.Push((const CHART *)len);

            toIndex1 += rightleft ? (-len) : len;
        }
    }

    // after
    if (rightleft)
    {
        if (endpos < lastIndex)
        {
            buffer.Push(tstring + endpos);
            buffer.Push((const CHART *)(lastIndex - endpos));
        }
    }
    else
    {
        if (lastIndex < endpos)
        {
            buffer.Push(tstring + lastIndex);
            buffer.Push((const CHART *)(endpos - lastIndex));
        }
    }

    if (oContext == 0) { ReleaseContext(pContext); }

    // join string
    result_length = 0;

    for (i = 0; i < buffer.GetSize(); i += 2)
    {
        result_length += (int)buffer[i + 1];
    }

    CBufferT <CHART> result_string;
    result_string.Prepare(result_length);
    result_string.Restore(0);

    if (rightleft)
    {
        for (i = buffer.GetSize() - 2; i >= 0; i -= 2)
        {
            result_string.Append(buffer[i], (int)buffer[i + 1]);
        }
    }
    else
    {
        for (i = 0; i < buffer.GetSize(); i += 2)
        {
            result_string.Append(buffer[i], (int)buffer[i + 1]);
        }
    }

    result_string.Append(0);

    result->m_result.Append(result_length, 3);
    result->m_result.Append(ntime);

    if (rightleft)
    {
        result->m_result.Append(result_length - toIndex1);
        result->m_result.Append(result_length - toIndex0);
    }
    else
    {
        result->m_result.Append(toIndex0);
        result->m_result.Append(toIndex1);
    }

    return result_string.Detach();
}

template <class CHART> inline void CRegexpT <CHART>::ReleaseString(CHART *tstring)
{
    if (tstring != 0) { free(tstring); }
}

template <class CHART> inline void CRegexpT <CHART>::ReleaseContext(CContext *pContext)
{
    if (pContext != 0) { delete pContext; }
}

//
// All implementations
//
template <int x> CAlternativeElxT <x>::CAlternativeElxT()
{
}

template <int x> int CAlternativeElxT <x>::Match(CContext *pContext) const
{
    // 0表示正则表达式为空，其它值表示正则表达式用 | 连接的pattern的个数
    if (m_elxlist.GetSize() == 0) { return 1; }

    // try all
    for (int n = 0; n < m_elxlist.GetSize(); ++n)
    {
        if (m_elxlist[n]->Match(pContext))
        {
            pContext->m_stack.Push(n);
            return 1;
        }
    }

    return 0;
}

template <int x> int CAlternativeElxT <x>::MatchNext(CContext *pContext) const
{
    if (m_elxlist.GetSize() == 0) { return 0; }

    int n = 0;

    // recall prev
    pContext->m_stack.Pop(n);

    // prev
    if (m_elxlist[n]->MatchNext(pContext))
    {
        pContext->m_stack.Push(n);
        return 1;
    }
    else
    {
        // try rest
        for (++n; n < m_elxlist.GetSize(); ++n)
        {
            if (m_elxlist[n]->Match(pContext))
            {
                pContext->m_stack.Push(n);
                return 1;
            }
        }

        return 0;
    }
}

// assertx.cpp: implementation of the CAssertElx class.
//
template <int x> CAssertElxT <x>::CAssertElxT(ElxInterface *pelx, int byes)
{
    m_pelx = pelx;
    m_byes = byes;
}

template <int x> int CAssertElxT <x>::Match(CContext *pContext) const
{
    int nbegin = pContext->m_nCurrentPos;
    int nsize  = pContext->m_stack.GetSize();
    int ncsize = pContext->m_capturestack.GetSize();
    int bsucc;

    // match
    if (m_byes) { bsucc =  m_pelx->Match(pContext); }
    else        { bsucc = !m_pelx->Match(pContext); }

    // status
    pContext->m_stack.Restore(nsize);
    pContext->m_nCurrentPos = nbegin;

    if (bsucc) { pContext->m_stack.Push(ncsize); }
    else       { pContext->m_capturestack.Restore(ncsize); }

    return bsucc;
}

template <int x> int CAssertElxT <x>::MatchNext(CContext *pContext) const
{
    int ncsize = 0;

    pContext->m_stack.Pop(ncsize);
    pContext->m_capturestack.Restore(ncsize);

    return 0;
}

// emptyelx.cpp: implementation of the CEmptyElx class.
//
template <int x> CEmptyElxT <x>::CEmptyElxT()
{
}

template <int x> int CEmptyElxT <x>::Match(CContext *) const
{
    return 1;
}

template <int x> int CEmptyElxT <x>::MatchNext(CContext *) const
{
    return 0;
}

// globalx.cpp: implementation of the CGlobalElx class.
//
template <int x> CGlobalElxT <x> ::CGlobalElxT()
{
}

template <int x> int CGlobalElxT <x>::Match(CContext *pContext) const
{
    return pContext->m_nCurrentPos == pContext->m_nBeginPos;
}

template <int x> int CGlobalElxT <x>::MatchNext(CContext *) const
{
    return 0;
}

// greedelx.cpp: implementation of the CGreedyElx class.
//
template <int x> CGreedyElxT<x>::CGreedyElxT(ElxInterface *pelx, int nmin, int nmax)
    : CRepeatElxT <x> (pelx, nmin)
{
    m_nvart = nmax - nmin;
}

template <int x> int CGreedyElxT <x>::Match(CContext *pContext) const
{
    if (!CRepeatElxT <x>::MatchFixed(pContext)) { return 0; }

    while (!MatchVart(pContext))
    {
        if (!CRepeatElxT <x>::MatchNextFixed(pContext)) { return 0; }
    }

    return 1;
}

template <int x> int CGreedyElxT <x>::MatchNext(CContext *pContext) const
{
    if (MatchNextVart(pContext)) { return 1; }

    if (!CRepeatElxT <x>::MatchNextFixed(pContext)) { return 0; }

    while (!MatchVart(pContext))
    {
        if (!CRepeatElxT <x>::MatchNextFixed(pContext)) { return 0; }
    }

    return 1;
}

template <int x> int CGreedyElxT <x>::MatchVart(CContext *pContext) const
{
    int n        = 0;
    int nbegin00 = pContext->m_nCurrentPos;
    int nsize    = pContext->m_stack.GetSize();
    int ncsize   = pContext->m_capturestack.GetSize();

    while (n < m_nvart && CRepeatElx::MatchForward(pContext)) { ++n; }

    pContext->m_stack.Push(ncsize);
    pContext->m_stack.Push(nsize);
    pContext->m_stack.Push(pContext->m_nCurrentPos);
    pContext->m_stack.Push(1);
    pContext->m_stack.Push(nbegin00);
    pContext->m_stack.Push(n);

    return 1;
}

template <int x> int CGreedyElxT <x>::MatchNextVart(CContext *pContext) const
{
    int n, nbegin00, nsize, ncsize;
    CSortedBufferT <int> nbegin99;
    pContext->m_stack.Pop(n);
    pContext->m_stack.Pop(nbegin00);
    pContext->m_stack.Pop(nbegin99);
    pContext->m_stack.Pop(nsize);
    pContext->m_stack.Pop(ncsize);

    if (n == 0) { return 0; }

    int n0 = n;

    if (!CRepeatElxT<x>::m_pelx->MatchNext(pContext)) { --n; }

    // not to re-match
    else if (pContext->m_nCurrentPos == nbegin00)
    {
        pContext->m_stack.Restore(nsize);
        pContext->m_capturestack.Restore(ncsize);
        pContext->m_nCurrentPos = nbegin00;

        return 0;
    }

    // fix 2012-10-26, thanks to chenlx01@sohu.com
    else
    {
        CContextShot shot(pContext);

        while (n < m_nvart && CRepeatElx::MatchForward(pContext)) { ++n; }

        if (nbegin99.Find(pContext->m_nCurrentPos) >= 0)
        {
            shot.Restore(pContext);
            n = n0;
        }
        else
        {
            nbegin99.Add(pContext->m_nCurrentPos);
        }
    }

    pContext->m_stack.Push(ncsize);
    pContext->m_stack.Push(nsize);
    pContext->m_stack.Push(nbegin99);
    pContext->m_stack.Push(nbegin00);
    pContext->m_stack.Push(n);

    return 1;
}

// indepelx.cpp: implementation of the CIndependentElx class.
//
template <int x> CIndependentElxT <x>::CIndependentElxT(ElxInterface *pelx)
{
    m_pelx = pelx;
}

template <int x> int CIndependentElxT <x>::Match(CContext *pContext) const
{
    int nbegin = pContext->m_nCurrentPos;
    int nsize  = pContext->m_stack.GetSize();
    int ncsize = pContext->m_capturestack.GetSize();

    // match
    int bsucc  = m_pelx->Match(pContext);

    // status
    pContext->m_stack.Restore(nsize);

    if (bsucc)
    {
        pContext->m_stack.Push(nbegin);
        pContext->m_stack.Push(ncsize);
    }

    return bsucc;
}

template <int x> int CIndependentElxT <x>::MatchNext(CContext *pContext) const
{
    int nbegin = 0, ncsize = 0;

    pContext->m_stack.Pop(ncsize);
    pContext->m_stack.Pop(nbegin);

    pContext->m_capturestack.Restore(ncsize);
    pContext->m_nCurrentPos = nbegin;

    return 0;
}

// listelx.cpp: implementation of the CListElx class.
//
template <int x> CListElxT <x>::CListElxT(int brightleft)
{
    m_brightleft = brightleft;
}

template <int x> int CListElxT <x>::Match(CContext *pContext) const
{
    // 0表示正则表达式为空，其它值表示正则表达式用 | 连接的pattern的个数
    if (m_elxlist.GetSize() == 0) { return 1; }

    // prepare
    int bol = m_brightleft ? m_elxlist.GetSize() : -1;
    int stp = m_brightleft ? -1 : 1;
    int eol = m_brightleft ? -1 : m_elxlist.GetSize();

    // from first
    int n = bol + stp;

    // match all
    while (n != eol)
    {
        if (m_elxlist[n]->Match(pContext))
        {
            n += stp;

            // 2019-04-22 zhuyadong 匹配到字符串末尾：表示用户输入符合正则表达式
            if (pContext->m_nCurrentPos == pContext->m_pMatchStringLength) { return 1; }
        }
        else
        {
            n -= stp;

            while (n != bol && !m_elxlist[n]->MatchNext(pContext)) { n -= stp; }

            if (n != bol) { n += stp; }
            else          { return 0; }
        }
    }

    return 1;
}

template <int x> int CListElxT <x>::MatchNext(CContext *pContext) const
{
    if (m_elxlist.GetSize() == 0) { return 0; }

    // prepare
    int bol = m_brightleft ? m_elxlist.GetSize() : -1;
    int stp = m_brightleft ? -1 : 1;
    int eol = m_brightleft ? -1 : m_elxlist.GetSize();

    // from last
    int n = eol - stp;

    while (n != bol && !m_elxlist[n]->MatchNext(pContext)) { n -= stp; }

    if (n != bol) { n += stp; }
    else          { return 0; }

    // match rest
    while (n != eol)
    {
        if (m_elxlist[n]->Match(pContext)) { n += stp; }
        else
        {
            n -= stp;

            while (n != bol && !m_elxlist[n]->MatchNext(pContext)) { n -= stp; }

            if (n != bol) { n += stp; }
            else          { return 0; }
        }
    }

    return 1;
}

// mresult.cpp: implementation of the MatchResult class.
//
template <int x> MatchResultT <x>::MatchResultT(CContext *pContext, int nMaxNumber)
{
    if (pContext != 0)
    {
        m_result.Prepare(nMaxNumber * 2 + 3, -1);

        // matched
        m_result[0] = 1;
        m_result[1] = nMaxNumber;

        for (int n = 0; n <= nMaxNumber; ++n)
        {
            int index = pContext->m_captureindex[n];

            //if( index < 0 ) continue;
            if (!CBracketElxT<char>::CheckCaptureIndex(index, pContext, n)) { continue; }

            // check enclosed
            int pos1 = pContext->m_capturestack[index + 1];
            int pos2 = pContext->m_capturestack[index + 2];

            // info
            m_result[n * 2 + 2] = pos1 < pos2 ? pos1 : pos2;
            m_result[n * 2 + 3] = pos1 < pos2 ? pos2 : pos1;
        }
    }
}

template <int x> inline int MatchResultT <x>::IsMatched() const
{
    return m_result.At(0, 0);
}

template <int x> inline int MatchResultT <x>::MaxGroupNumber() const
{
    return m_result.At(1, 0);
}

template <int x> inline int MatchResultT <x>::GetStart() const
{
    return m_result.At(2, -1);
}

template <int x> inline int MatchResultT <x>::GetEnd() const
{
    return m_result.At(3, -1);
}

template <int x> inline int MatchResultT <x>::GetGroupStart(int nGroupNumber) const
{
    return m_result.At(2 + nGroupNumber * 2, -1);
}

template <int x> inline int MatchResultT <x>::GetGroupEnd(int nGroupNumber) const
{
    return m_result.At(2 + nGroupNumber * 2 + 1, -1);
}

template <int x> MatchResultT <x> &MatchResultT <x>::operator = (const MatchResultT <x> &result)
{
    m_result.Restore(0);

    if (result.m_result.GetSize() > 0) { m_result.Append(result.m_result.GetBuffer(), result.m_result.GetSize()); }

    return *this;
}

// posselx.cpp: implementation of the CPossessiveElx class.
//
template <int x> CPossessiveElxT<x>::CPossessiveElxT(ElxInterface *pelx, int nmin, int nmax)
    : CGreedyElxT <x> (pelx, nmin, nmax)
{
}

template <int x> int CPossessiveElxT <x>::Match(CContext *pContext) const
{
    int nbegin = pContext->m_nCurrentPos;
    int nsize  = pContext->m_stack.GetSize();
    int ncsize = pContext->m_capturestack.GetSize();
    int bsucc  = 1;

    // match
    if (!CRepeatElxT <x>::MatchFixed(pContext)) { bsucc = 0; }
    else
    {
        while (!CGreedyElxT <x>::MatchVart(pContext))
        {
            if (!CRepeatElxT <x>::MatchNextFixed(pContext))
            {
                bsucc = 0;
                break;
            }
        }
    }

    // status
    pContext->m_stack.Restore(nsize);

    if (bsucc)
    {
        pContext->m_stack.Push(nbegin);
        pContext->m_stack.Push(ncsize);
    }

    return bsucc;
}

template <int x> int CPossessiveElxT <x>::MatchNext(CContext *pContext) const
{
    int nbegin = 0, ncsize = 0;

    pContext->m_stack.Pop(ncsize);
    pContext->m_stack.Pop(nbegin);

    pContext->m_capturestack.Restore(ncsize);
    pContext->m_nCurrentPos = nbegin;

    return 0;
}

// reluctx.cpp: implementation of the CReluctantElx class.
//
template <int x> CReluctantElxT<x>::CReluctantElxT(ElxInterface *pelx, int nmin, int nmax)
    : CRepeatElxT <x> (pelx, nmin)
{
    m_nvart = nmax - nmin;
}

template <int x> int CReluctantElxT <x>::Match(CContext *pContext) const
{
    if (!CRepeatElxT <x>::MatchFixed(pContext)) { return 0; }

    while (!MatchVart(pContext))
    {
        if (!CRepeatElxT <x>::MatchNextFixed(pContext)) { return 0; }
    }

    return 1;
}

template <int x> int CReluctantElxT <x>::MatchNext(CContext *pContext) const
{
    if (MatchNextVart(pContext)) { return 1; }

    if (!CRepeatElxT <x>::MatchNextFixed(pContext)) { return 0; }

    while (!MatchVart(pContext))
    {
        if (!CRepeatElxT <x>::MatchNextFixed(pContext)) { return 0; }
    }

    return 1;
}

template <int x> int CReluctantElxT <x>::MatchVart(CContext *pContext) const
{
    pContext->m_stack.Push(0);

    return 1;
}

template <int x> int CReluctantElxT <x>::MatchNextVart(CContext *pContext) const
{
    int n = 0, nbegin = pContext->m_nCurrentPos;

    pContext->m_stack.Pop(n);

    if (n < m_nvart && CRepeatElxT <x>::m_pelx->Match(pContext))
    {
        while (pContext->m_nCurrentPos == nbegin)
        {
            if (!CRepeatElxT <x>::m_pelx->MatchNext(pContext)) { break; }
        }

        if (pContext->m_nCurrentPos != nbegin)
        {
            ++n;

            pContext->m_stack.Push(nbegin);
            pContext->m_stack.Push(n);

            return 1;
        }
    }

    while (n > 0)
    {
        pContext->m_stack.Pop(nbegin);

        while (CRepeatElxT <x>::m_pelx->MatchNext(pContext))
        {
            if (pContext->m_nCurrentPos != nbegin)
            {
                pContext->m_stack.Push(nbegin);
                pContext->m_stack.Push(n);

                return 1;
            }
        }

        --n;
    }

    return 0;
}

// repeatx.cpp: implementation of the CRepeatElx class.
//
template <int x> CRepeatElxT <x>::CRepeatElxT(ElxInterface *pelx, int ntimes)
{
    m_pelx   = pelx;
    m_nfixed = ntimes;
}

template <int x> int CRepeatElxT <x>::Match(CContext *pContext) const
{
    return MatchFixed(pContext);
}

template <int x> int CRepeatElxT <x>::MatchNext(CContext *pContext) const
{
    return MatchNextFixed(pContext);
}

template <int x> int CRepeatElxT <x>::MatchFixed(CContext *pContext) const
{
    if (m_nfixed == 0) { return 1; }

    int n = 0;

    while (n < m_nfixed)
    {
        if (m_pelx->Match(pContext)) { ++n; }
        else
        {
            --n;

            while (n >= 0 && !m_pelx->MatchNext(pContext)) { --n; }

            if (n >= 0) { ++n; }
            else        { return 0; }
        }
    }

    return 1;
}

template <int x> int CRepeatElxT <x>::MatchNextFixed(CContext *pContext) const
{
    if (m_nfixed == 0) { return 0; }

    // from last
    int n = m_nfixed - 1;

    while (n >= 0 && !m_pelx->MatchNext(pContext)) { --n; }

    if (n >= 0) { ++n; }
    else        { return 0; }

    // match rest
    while (n < m_nfixed)
    {
        if (m_pelx->Match(pContext)) { ++n; }
        else
        {
            --n;

            while (n >= 0 && !m_pelx->MatchNext(pContext)) { --n; }

            if (n >= 0) { ++n; }
            else        { return 0; }
        }
    }

    return 1;
}

// Regexp
typedef CRegexpT <char> CRegexpA;
typedef CRegexpT <unsigned short> CRegexpW;

#if defined(_UNICODE) || defined(UNICODE)
    typedef CRegexpW CRegexp;
#else
    typedef CRegexpA CRegexp;
#endif

#endif//__DEELX_REGEXP__H__
